[백준(BOJ)] 7562번 나이트의 이동 C++

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

7562번: 나이트의 이동

 

 

어떤 문제인가?

아주 간단한 문제이다.

기존의 상, 하, 좌, 우로 그래프를 탐색하던 방법에서

나이트의 이동 방식처럼만 움직이며 탐색하면 되는 문제이다.

나이트의 시작 위치와 도착 위치가 주어졌을 때

도착하는 최소 횟수를 출력하면 된다.

 

접근 방법

 

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

위 두 배열은 나이트가 x좌표 y좌표로 이동할 수 있는 거리들이다.

 

int l;
int visited[301][301];
int graph[301][301];

체스판의 크기 l과 방문 여부를 저장할 이차원 배열, 나이트가 움직일 이차원 배열을 선언해준다.

 

void bfs(int startX, int startY, int endX, int endY) {
    queue<pair<int, int>> q;
    q.push({startX, startY});

    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        q.pop();

        if (x == endX && y == endY) {
            cout << graph[x][y] << endl;
            return;
        }

        for (int i = 0; i < 8; i++) {
            int x2 = x + dx[i];
            int y2 = y + dy[i];

            if (x2 < 0 || y2 < 0 || x2 >= l || y2 >= l) {
                continue;
            }

            if (!visited[x2][y2]) {
                visited[x2][y2] = true;
                q.push({x2, y2});
                graph[x2][y2] = graph[x][y] + 1;
            }
        }
    }
}

bfs의 방식은 다른 문제와 거의 다를 것이 없다.

큐를 사용해 탐색해나가며 현재 나이트의 x좌표와 y좌표가 도착 지점의 x좌표와 y좌표와 일치하면 이동 횟수를 출력하고 함수가 종료된다.

 

예외처리는 나이트가 l*l 체스판을 벗어나지만 않도록 해주면 된다.

이동한 나이트의 위치를 방문하지 않았다면, 방문처리를 해주고 좌표를 큐에 추가해준다.

그리고 이동 횟수는 기존에 모든 체스판이 0으로 초기화되어 있다.

따라서 이동 횟수는 그냥 기존의 좌표에 저장되어있는 값 + 1을 해주면 된다.

 

graph [ 3 ] [ 1 ] = 4의 뜻은 나이트가 (3, 1)까지 이동하는데 4번 걸린다는 것이다.

 

 

int t;
cin >> t;

테스트 케이스의 개수인 t를 선언하고 입력받는다.

 

while (t--) {
    cin >> l;

    int a, b, c, d;
    cin >> a >> b >> c >> d;

    bfs(a, b, c, d);
    fill(&visited[0][0], &visited[300][301], false);
    fill(&graph[0][0], &graph[300][301], 0);

}

t번 동안 반복문을 돌 것이다.

나이트의 시작 위치의 좌표를 a, b로 도착 위치를 c, d로 간단하게 입력받았다.

그리고 이것들을 bfs함수의 파라미터로 넘겨 탐색을 시작할 것이다.

그리고 bfs가 끝날 때마다 fill함수로 사용했던 방문 배열과 체스판을 초기화시켜준다.

 

이렇게 반복문이 끝나면 모든 테스트 케이스가 끝!

 

 

무엇이 어려웠는가?

dx, dy 배열만 기존의 상, 하, 좌, 우 방식과 다를 뿐이었다.

어려움 없이 문제를 해결할 수 있었다.