[백준 알고리즘] 7561번: 나이트의 이동
July 01, 2020
https://www.acmicpc.net/problem/7562
문제
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, …, l-1} × {0, …, l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 몇 번만에 이동할 수 있는지 출력한다.
풀이
BFS를 이용해서 풀 수 있는 문제였다. 나이트가 움직일 수 있는 좌표는 총 8종류가 있는데, 이 조합을 xdir, ydir 배열에 저장해둔다. 좌표를 이동하는 문제에서 어떤 노드의 자녀노드들은 다음에 이동할 수 있는 모든 좌표를 의미하기 때문에 어떤 좌표 (x, y)에 배열에 저장된 조합들을 계산해서 얻은 다음 좌표들은 서로 인접한 노드들이 된다. 따라서 목적지에 해당하는 좌표가 나올 때까지 BFS를 수행하며 만들어지는 트리의 depth 를 계산하면 몇 번을 이동시켜서 목적지로 갈 수 있는지 알 수 있게 된다.
그런데 이 문제에서는 인접리스트를 직접적으로 만들어 사용하지 않기 때문에 depth를 확인하기 위해서 다른 장치를 만들어야할 필요가 있다. BFS에서 한 depth는 해당 depth에 위치한 모든 노드들의 탐색이 끝나면 다음 dpeth로 이동하게 된다. 이 점을 이용해서 첫 depth부터 큐에 들어가있는 노드의 수를 기억해 해당 숫자만큼의 탐색이 끝났을 때 depth를 증가시켜준다면 depth를 계속해서 기록해줄 수 있을 것이다.
예를 들어 (0, 0) 좌표에서 시작했을 때 큐에는 이 좌표만 들어가있기 때문에 1번만 탐색하면 다음 depth로 이동한다. 그리도 다음 depth에서는 최대 8개의 가능한 다음 좌표들이 들어가게 된다. 이 때 큐에는 이 좌표들만 들어있을 것이기 때문에 큐의 크기를 기억해두고 해당 노드들에 대한 탐색이 모두 끝나면 depth를 증가시켜주는 방식이다.
코드
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int border;
bool visited[301][301] = {0};
/* 방문여부 기록 초기화 */
void clearVisited(){
for (int i = 0; i < border; i++){
for (int j = 0; j < border; j++){
visited[i][j] = false;
}
}
}
/* 말을 놓을 수 있는 자리인지 확인 */
bool isOverBorder(int x, int y){
return x < 0 || y < 0 || x >= border || y >= border;
}
/* 정답 확인 */
bool isSolution(int x1, int y1, int x2, int y2){
return x1 == x2 && y1 == y2;
}
int bfs(int startX, int startY, int destX, int destY){
int xdir[] = {-2, -2, -1, -1, 1, 1, 2, 2}; // 나이트의 이동범위에 대한 x 좌표 조합
int ydir[] = {1, -1, 2, -2, 2, -2, 1, -1}; // 나이트의 이동범위에 대한 y 좌표 조합
queue<pair<int, int>> q;
int move = 0;
visited[startY][startX] = true;
q.push({startX, startY});
while (!q.empty()){
unsigned long size = q.size(); // 현재 큐의 크기를 통해서 depth 계산하기
for(int k = 0 ; k < size ; k++){
int nodeX = q.front().first; // 큐에서 새로 꺼낸 위치의 x 좌표
int nodeY = q.front().second; // 큐에서 새로 꺼낸 위치의 y 좌표
q.pop();
if (isSolution(nodeX, nodeY, destX, destY)) return move; // 정답을 찾으면 결과 리턴
for (int i = 0; i < 8; i++){ // 말을 놓을 수 있는 다음 좌표 계산. 총 8개의 위치가 가능
int nextX = nodeX + xdir[i];
int nextY = nodeY + ydir[i];
if (!isOverBorder(nextX, nextY) && !visited[nextY][nextX]){ // 말을 놓을 수 있는 좌표이고 탐색한 적이 없는 자표라면 큐에 넣기
q.push({nextX, nextY});
visited[nextY][nextX] = true;
}
}
}
move++;
}
return 0;
}
int main(){
int T;
scanf("%d", &T);
while (T--){
int currX, currY, destX, destY;
clearVisited();
scanf("%d", &border);
scanf("%d %d", &currX, &currY);
scanf("%d %d", &destX, &destY);
int result = bfs(currX, currY, destX, destY); // bfs 수행
printf("%d\n", result);
}
}
