[백준/c++] 7562번: 나이트의 이동

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

7562번: 나이트의 이동

 

문제 요약

 

나이트가 한 번에 이동할 수 있는 칸

나이트가 이동하려고 하는 칸이 주어지고, 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

 

범위

 

체스판의 한 변의 길이 l(4 ≤ l ≤ 300)

 

체스판의 크기는 l × l

 

 

 

---

 

이 문제는 최단 이동 경로를 구하는 문제와 비슷하다. 최단 이동 경로 == 최소 이동 횟수와 동일하다 (거리가 1이므로, +1)

최단 이동 경로를 구하려면 BFS 알고리즘을 사용하면 된다.

 

이동할 수 있는 위치는 

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

문제에서 보여준 그림에서 중앙 위치를 (0, 0)으로 잡고 상대 값을 구해주면 위와 같은 좌표들이 찍힌다.

 

시작 위치를 큐에 넣고 시작한다. 

방문과 거리를 동시에 체크/업데이트할 수 있도록 거리를 의미하는 2차원 배열 dis를 사용했다. -1는 방문하지 않은/처음 위치로부터의 거리도 없는 좌표를 의미한다. 

 

이동할 수 있는 좌표로 이동하되 아래의 조건에 맞으면 그냥 지나간다.

 - 체스판 내에 존재하는가? 바깥이라면 continue(패스)

 - 방문한 곳인가? 방문했다면 continue(패스)

 

위의 조건에 맞지 않은 좌표라면 부모 좌표(x, y)에서 +1을 해준다. (이동거리 값 증가)

이렇게 모든 좌표로 이동하고 큐가 비었다면 나와서 이동 거리 값을 저장한 dis 배열에서 도착 좌표를 넣어서 출력해준다.

 

#include <iostream>
#include <queue>
using namespace std;
int t, I, startX, startY, endX, endY;
int dir[8][2] = {{-1, 2}, {-2, 1}, {1, 2}, {2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}};
int dis[302][302] = {-1};

void BFS(){
    queue<pair<int, int>> q;
    q.push({startX, startY});
    dis[startX][startY] = 0;
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int i=0; i<8; i++){
            int dx = x + dir[i][0];
            int dy = y + dir[i][1];
            if(dx < 0 || dy < 0 || dx > I || dy > I) continue;
            if(dis[dx][dy] != -1) continue; //방문한 곳이므로 패스
            dis[dx][dy] = dis[x][y] + 1;
            q.push({dx, dy});
        }
    }
    cout << dis[endX][endY] << '\n';
}

void input(){
    cin >> t;
    while(t--){
        cin >> I;
        cin >> startX >> startY >> endX >> endY;
        for(int i=0; i<I; i++) for(int j=0; j<I; j++) dis[i][j] = -1; //거리(방문체크) 초기화
        BFS();
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    return 0;
}

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!