백준 알고리즘 7562번 나이트의 이동 C언어

문제

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

입력

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

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

출력

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

 

문제 풀이

1. 처음에는 dfs로 풀어야 하는줄 알았는데 그렇게 하면 8개의 방향을 한 번에  검사하는 게 아니라 하나 검사하고 그 점에 대해서 다시 8개의 방향을 검사하여 아래와 같은 결과가 나오게 된다. 그래서 BFS 로 풀어야한다.

 

2. 왜인지는 모르겠으나 엄청 오래 걸렸음 ㅠ 테스트 케이스는 다 작동되는데 제출만 하면 틀렸습니다가 나와버림

다음 케이스로 넘어갈 때 큐에 자료가 남아있을 수 있다고 해서 큐를 다 비우고 나서 결과값을 출력했다.

그리고 당연히 chess_board도 초기화했ㄴ다. 근데 아직까지도 틀린 이유는 모르겠당.

어찌저찌 하다보니 성공했다;; 그래도 2시간 정도는 걸린 것 같다.

 

#include<stdio.h>
#include<string.h>
#define SZ 301
#define QUE_SZ 90001
 
int chess_board[SZ][SZ] = { 0 };
int test_case, chess_size;
 
int vectY[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };
int vectX[8] = { -2, -1, 1, 2, 2, 1, -1, -2 };
 
struct node {
    int x;
    int y;
};
struct node queue[QUE_SZ];
int tail = 0;
int head = 0;
 
void enque(int a, int b) {
    struct node temp;
    temp.x = a; temp.y = b;
    queue[tail] = temp;
    tail = (tail + 1) % QUE_SZ;
}
 
struct node deque() {
    struct node temp = queue[head];
    head = (head + 1) % QUE_SZ;
    return temp;
}
 
int isQueEmpty() {
    return (head == tail) ? 1 : 0;
}
 
void do_bfs() {
 
    struct node temp;
    while (isQueEmpty() == 0) {
        temp = deque();
        int a = temp.x; int b = temp.y;
 
        int nextX; int nextY;
        for (int i = 0; i < 8; i++) {
            nextX = a + vectX[i];
            nextY = b + vectY[i];
 
            if (nextX >= 0 && nextY >= 0 && nextX < chess_size && nextY < chess_size) {
                if (chess_board[nextX][nextY] == 0) {
                    chess_board[nextX][nextY] = chess_board[a][b] + 1;
                    enque(nextX, nextY);
                }
            }
        }
    }
    return;
}
 
void solution(int chess_start_x, int chess_start_y, int chess_dst_x, int chess_dst_y) {
    chess_board[chess_start_x][chess_start_y] = 1;
    enque(chess_start_x, chess_start_y);
    do_bfs();
    printf("%d\n", chess_board[chess_dst_x][chess_dst_y] - 1);
    return;
}
 
int main() {
    scanf("%d", &test_case);
    int chess_start_x, chess_start_y, chess_dst_x, chess_dst_y;
 
    for (int i = 0; i < test_case; i++) {
 
        scanf("%d", &chess_size);
        scanf("%d %d", &chess_start_x, &chess_start_y);
        scanf("%d %d", &chess_dst_x, &chess_dst_y);
 
        memset(chess_board, 0, sizeof(chess_board));
        solution(chess_start_x, chess_start_y, chess_dst_x, chess_dst_y);
    }
}