[BFS | 기본 문제] 7562번 : 나이트의 이동

https://www.acmicpc.net/problem/7562

---

 걸린 시간 

풀이 생각하고 구현 : 30분

디버깅 : 1시간 반 정도

 

 생각

- 일반적인 BFS문제에서 체크하는 좌표가 8개로 늘어난 것

 

 구현 

- 출력을 한번에 해야하는 줄 알고 또다른 q에 저장해서 테케 다돌고 한번에 출력하게 함

- 목적지를 찾으면 더이상 돌지않게 하려고 조건문을 추가했는데 범위가 작아서 그냥 다 돌고 목적지의 dist를 출력하도록 하면 코드는 더 간결하다.

---

 구현 코드 

#include<iostream>
#include<queue>
#include<algorithm>

using namespace std;

int l;
int dist[301][301];
int dx[8] = { 1,1,2,2,-1,-1,-2,-2 };
int dy[8] = { 2,-2,1,-1,2,-2,1,-1 };

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int testCase;
	cin >> testCase;

	queue<pair<int, int>> q;
	queue<int> result;

	while (testCase-- != 0){
		//초기화
		fill(&dist[0][0], &dist[300][300], -1);
		//체스판 길이 입력
		cin >> l;
		//현재 위치 입력
		int x, y;
		cin >> x >> y;
		q.push({ x,y });
		dist[x][y] = 0;
		//목적지 입력
		int dist_x, dist_y;
		cin >> dist_x >> dist_y;
		if (dist_x == x && dist_y == y){
			result.push(dist[dist_x][dist_y]);
			continue;
		}
		while (!q.empty()){
			auto cur = q.front(); q.pop();

			for (int dir = 0; dir < 8; dir++){
				int nx = cur.first + dx[dir];
				int ny = cur.second + dy[dir];

				if (nx >= l || ny >= l || nx < 0 || ny < 0) continue;
				if (dist[nx][ny] >= 0) continue;
				dist[nx][ny] = dist[cur.first][cur.second] + 1;
				q.push({ nx,ny });
				if (nx == dist_x && ny == dist_y)
				{
					result.push(dist[dist_x][dist_y]);
					break;
				}
			}
		}
	}
	while (!result.empty()){
		cout << result.front() << "\n";
		result.pop();
	}
}

 

 디버깅 

- 제출1( 틀림 ) : 목적지와 출발지가 같은 경우, 0 을 출력해야하는데 아무 것도 출력하지 않음

- 제출2 (틀림) : 목적지 == 출발지 조건문을 넣어주는데 break로 빠져나와서 while문 자체를 빠져나가버림 

나는 왜 while문 한케이스만 끝난다고 생각했을까... 

 

 해결 

그런 줄도 모르고 반례를 엄청 찾았지만 알지 못해서 질문 게시판에 올려서 해결함

 

 리뷰 

요즘  문제를 풀수록 알고리즘이 아니라 그냥 기본 개념 자체..구현력 자체가 많이 부족하다고 느낀다.

익숙해진 알고리즘들은 문제를 보고 어떻게 풀지 어느정도 풀이까진 빠르게 쓰고 구현도 빨리 하는데

이런 기본적인 것들을 해결하지 못해서 계속 디버깅하는 시간이 너무 길다.. 기초 문제들로 연습을 해야겠다는 생각이 들었다.