[C++] 백준 알고리즘 7562번 (나이트의 이동)

문제

---

이번에 다뤄볼 문제는 7562번 문제 '나이트의 이동'입니다.

나이트의 이동 문제에서 연습해야하는 key-point는 BFS와 큐입니다.

 

BFS는 너비 우선 탐색을 뜻하는데요.

너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다.

큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로,

먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다.

 

나이트가 이동 할 수 있는 8방향을 dirX,dirY배열에 입력합니다.
그리고 나이트의 다음 탐색 가능 위치를 큐에 넣고 visited 2차원 배열에 방문 횟수를 기록해 줍니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include <iostream>
using namespace std;
 
 
int dirX[8] = {-2,-1,-2,-1,1,2,1,2};
int dirY[8] = {1,2,-1,-2,-2,-1,2,1};
 
int q[90000][2];
int front = 0, rear = 0;
 
int main() {
    int n, size, s_x, s_y, d_x, d_y;
    int x = 0 ,y = 0,xx = 0, yy = 0;
 
 
    cin >> n;
     
 
    for (int i = 0; i < n; i++) {
 
        int visited[301][301] = { 0 };
        front = 0; rear = 0;
 
 
        cin >> size;
        cin >> s_x >> s_y;
        cin >> d_x >> d_y;
 
        q[rear][0] = s_x; q[rear++][1] = s_y;
         
        while (front != rear) {
            x = q[front][0]; y = q[front++][1];
 
            if (d_x == x && d_y == y) break;
 
            for (int j = 0; j < 8; j++) {
                xx = x + dirX[j]; yy = y + dirY[j];
                if ( xx>size-1 || yy>size-1|| xx<0 || yy<0 ) continue;
                if (visited[xx][yy] == 0 || visited[xx][yy] > visited[x][y] + 1) {
                    q[rear][0] = xx; q[rear++][1] = yy;
                    visited[xx][yy] = visited[x][y] + 1;
                }
            }
        }
        cout << visited[d_x][d_y] << endl;
    }
    return 0;
}