백준[7562] - 나이트의 이동

문제

백준 7562 문제 보기

접근 방법

주어진 점에서 도착지까지 몇 번만에 이동할 수 있는지 출력하는 문제로 bfs로 해결 가능하다.

• 한번에 움직일 수 있는 좌표 차이를 계산해 배열에 저장
• 이를 활용해 방문 여부를 체크하며 완전 탐색을 진행
• 도착지면 정답 출력

코드

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

int I, T;
int map[301][301];
int visited[301][301];
int dr[8] = {-1, -2, -2, -1, 1, 2, 2, 1};
int dc[8] = {-2, -1, 1, 2, 2, 1, -1, -2};

struct location {
    // row
    int cr;
    // column
    int cc;
    // count
    int cnt;
};

queue<location> q;

int main() {
    cin >> T;
    while(T--) {
        int desR, desC, r, c;
        // map과 visted 배열 초기화
        memset(map, 0, sizeof(map));
        memset(visited, 0, sizeof(visited));
        // 큐가 비워져 있는지 확인
        while(!q.empty()){
            q.pop();
        }
        cin >> I;
        cin >> r >> c >> desR >> desC;
        location loc;
        loc.cr = r;
        loc.cc = c;
        loc.cnt = 0;
        // 방문체크
        visited[r][c] = 1;
        q.push(loc);
        while(!q.empty()) {
            int r = q.front().cr;
            int c = q.front().cc;
            int cnt = q.front().cnt;
            q.pop();
            // 도착 지점 확인
            if(r == desR && c == desC) {
                cout << cnt << endl;
                break;
            }
            // 8 방향으로 좌표 이동
            for(int i = 0; i < 8; i ++) {
                int nextR = r + dr[i];
                int nextC = c + dc[i];
                // 좌표가 범위안에 존재 확인
                if(nextC >= 0 && nextR >= 0 && nextC < I && nextR < I) {
                    // 방문하지 않았다면
                    if(!visited[nextR][nextC]) {
                        visited[nextR][nextC] = 1;
                        q.push({nextR, nextC, cnt + 1});
                    }
                }
            }
        }
    }
    return 0;
}