[백준/BOJ][C++] 7562번 : 나이트의 이동(DFS, BFS)

7562번: 나이트의 이동

문제

체스판 위에 한 나이트가 놓여 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0,..., l-1} × {0,..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

접근 방법

<DFS? BFS?>

일단 그래프 탐색 문제라는 느낌은 오지만 DFS를 사용할 것인지 BFS를 사용할 것인지 정해야 한다. 사실 나도 아직 이해도가 부족해서 문제마다 가장 효율적인 선택을 할 수는 없지만, 이 문제에서 알 수 있는 사실은 최단 거리를 구할 땐 DFS보다는 BFS가 유용하다는 점이다. 

 

DFS로 최단 거리를 구하려고 한다면, 조건을 충족할 때까지 재귀를 돌리고 그 모든 경우의 수 중에서 최솟값을 구하는 방식으로 해야 한다. BFS로 최단거리를 구한다면, 처음부터 모든 경우의 수에 똑같이 +1씩 해주면서 하나라도 조건을 충족한다면 BFS를 종료하기 때문에, 최단 거리를 찾을 때는 BFS가 DFS보다 효율적이다.

주의할 점

일반적인 유형의 문제라 크게 주의할 점은 없다.

 

다만 내 코드의 변수 명명이 다소 헷갈릴 수는 있다. 고쳐야 하는데 이상한 습관이 들어버렸다..

코드

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

using namespace std;
int n;
int x, y, tox, toy;
int check[301][301] = {0};
int visited[301][301] = {0};
int movex[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int movey[8] = {2, 1, -1, -2, -2, -1, 1, 2};

void bfs(int x, int y){
	queue<pair<int, int > > q;
	q.push({x, y});
	while(!q.empty()){
		int nx = q.front().first;
		int ny = q.front().second;
		visited[nx][ny] = 1;
		q.pop();
		if(nx == tox && ny == toy){
			cout << check[nx][ny] << "\n";
			while(!q.empty()){
				q.pop();
			}
			break;
		}
		for(int i = 0; i < 8; i++){
			int dx = nx + movex[i];
			int dy = ny + movey[i];
			if(dx >= 0 && dx < n && dy >= 0 && dy < n && visited[dx][dy] == 0){
				q.push({dx, dy});
				visited[dx][dy] = 1;
				check[dx][dy] = check[nx][ny] + 1;
			}
		}
	}
}
int main(){
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int t;
   cin >> t;
   for(int i = 0; i < t; i++){
      cin >> n;
      cin >> x >> y;
      cin >> tox >> toy;
      bfs(x, y);
      for(int j = 0; j < 301; j++){
         for(int m = 0; m < 301; m++){
         	visited[j][m] = 0;
            check[j][m] = 0;
         }
      }
   }
}