[백준 7562번 나이트의 이동] 문제풀이

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

문제

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

입력

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

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

출력

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

 

- 해결 아이디어

• 큐를 이용해서 BFS 구현 
• 체스판 배열을 만들어서 요소는 해당 지점까지의 최소 이동 횟수를 저장

- 해결 방법

1. 처음에 시작 위치를 큐에 삽입

2. 큐를 pop해서 현재 위치를 가져옴.

3. 현재 위치 + 8가지 방향으로 이동했을 때 위치가 체스판 안에 있고, 방문하지 않은 칸(동일한 지점을 방문하더라도 이후에 진행된 요소들은 무조건 해당 지점의 최소 이동 횟수보다 크거나 같기 때문에 대소 비교를 하지 X)이라면 큐에 삽입하고 체스판 배열 요소에 현재 위치의 최소 이동 횟수 + 1을 저장 

4. 2,3번 과정을 반복하다가 큐가 비거나 최종 위치에 방문한다면 최종 위치의 최소 이동 횟수를 반환

 

- 정답 코드 (C++)

// 백준 문제 : 나이트의 이동
#include <iostream>
#include <queue>
#include <vector>
// #include <cmath>

using namespace std;

int dy[8] = {-2,-1,1,2,2,1,-1,-2}; // 12시부터 시계방향으로 
int dx[8] = {1,2,2,1,-1,-2,-2,-1};
queue<pair<int,int>> qu;

int bfs(int i,int l,pair<int,int> startPos, pair<int,int> endPos,vector<vector<int>> board){
    if(startPos == endPos){
        return 0;
    }
    board[startPos.first][startPos.second] = 0;
    qu.push({startPos.first,startPos.second});

    while(!qu.empty() && board[endPos.first][endPos.second] == -1){
        auto cur = qu.front(); qu.pop();
        // float curDistance  = sqrt(pow(cur.first-endPos.first,2)+pow(cur.second-endPos.second,2));
        // cout << "현재 큐 요소 : "<<cur.first <<","<< cur.second  << "{" << board[cur.first][cur.second]<< "}"<< endl;
        for(int j=0;j<8;j++){
            int cy = cur.first + dy[j];
            int cx = cur.second + dx[j];
            if(cy >= 0 && cy < l && cx >= 0 && cx < l && board[cy][cx] == -1){
                // float cDistance = sqrt(pow(cy-endPos.first,2)+pow(cx-endPos.second,2));
                // if(cDistance < curDistance || cDistance <= sqrt(5)){ // 시간, 공간 복잡도 측면에서 개선 X -> 오히려 오답 
                board[cy][cx] = board[cur.first][cur.second] + 1;
                // cout << "현재 큐에 삽입되는 요소 : "<< cy << "," << cx << endl;
                qu.push({cy,cx});
                // }
            }
        }
    }

    qu = queue<pair<int,int>>();
    return board[endPos.first][endPos.second];
}

int main(){
    int t;
    cin >> t;

    vector<int> l(t,0);
    vector<pair<int,int>> startPos(t,{0,0});
    vector<pair<int,int>> endPos(t,{0,0});
    for(int i=0;i<t;i++){
        cin >> l[i];

        cin >> startPos[i].first >> startPos[i].second;

        cin >> endPos[i].first >> endPos[i].second;
    }

    for(int i=0;i<t;i++){
        vector<vector<int>> board(l[i],vector<int>(l[i],-1));
        int result = bfs(i,l[i],startPos[i],endPos[i],board);
        cout << result << endl;
    }
}