[BFS/DFS] C11 백준 7562 나이트의 이동 풀이

문제

• 7562

풀이 과정

• 먼저 나이트의 이동 방향(좌표)을 확인하고, 입력으로 시작점과 도착지점을 주기 때문에 -> bfs로 풀자! 라고 생각이 듬
  • 딱히 어려운건 없었당
• BFS, 자료구조는 큐!

#include <stdio.h>

#define MAX 301

typedef struct Que {
    int x;
    int y;
} Q;

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

int l;
int map[MAX][MAX];

Q que[MAX*MAX];
int front;
int rear;

void enqueue(int x, int y) {
    que[rear].x = x;
    que[rear].y = y;
    rear++;
}

Q dequeue() {
    return que[front++];
}

int bfs(int a, int b) {
    while (front < rear) {
        Q cur = dequeue();
        
        if (cur.x == a && cur.y == b) {
            return map[cur.x][cur.y] - 1;
        }
        
        for (int i=0; i<8; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < l && ny >= 0 && ny < l && map[nx][ny] == 0) {
                map[nx][ny] = map[cur.x][cur.y] + 1;
                enqueue(nx, ny);
            }
        }
    }
    return -1;
}

int main() {
    int tc;
    scanf("%d", &tc);
    
    while (tc--) {
        scanf("%d", &l);
        
        for (int i=0; i<l; i++) {
            for (int j=0; j<l; j++) {
                map[i][j] = 0;
            }
        }
        front = 0;
        rear = 0;
        
        int x = 0, y = 0;
        scanf("%d %d", &x, &y);
        map[x][y] = 1;
        enqueue(x, y);
        
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        int result = bfs(a, b);
        
        printf("%d\n", result);
    }
    return 0;
}