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

문제: www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

 

문제풀이

 

BFS를 이용하여 최단거리를 구하는 문제이다.

 

다른 너비우선탐색과 다르게 dx, dy가 상하좌우가 아닌 나이트 말이 움직일 수 있는 수로 고쳐주면 된다.

 

int dx[4] = {-1,1,0,0}  -->  int dx[8] = {-2,-2,-1,-1,1,1,2,2}

int dy[4] = {0,0,-1,1}  -->  int dy[8] = {-1,1,-2,2,-2,2,-1,1}

 

 

코드

#include <iostream>
#include <queue>

using namespace std;

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

int main(){
    ios::sync_with_stdio(false); cin.tie(NULL);

    int t;
    cin>>t;

    while(t--){
        int l,sx,sy,ex,ey;
        cin>>l>>sx>>sy>>ex>>ey; //크기, 시작좌표, 도착좌표

        for(int i=0; i<l; i++){ //다음 테스트케이스를 위해 거리 배열 초기화
            fill(dist[i], dist[i]+l, -1);
        }

        queue<pair<int,int>> q;
        q.push({sx,sy});
        dist[sx][sy] = 0;

        while(!q.empty()){
            pair<int,int> cur = q.front();
            q.pop();

            if(cur == make_pair(ex,ey)){
                cout<<dist[cur.first][cur.second]<<"\n";
                break;
            }

            for(int dir=0; dir<8; dir++){
                int nx = cur.first + dx[dir];
                int ny = cur.second + dy[dir];

                if(nx<0||nx>=l||ny<0||ny>=l) continue;
                if(dist[nx][ny]>=0) continue;

                q.push({nx,ny});
                dist[nx][ny] = dist[cur.first][cur.second] + 1;
            }
        }

        while(!q.empty()) //다음 테스트케이스르 위해 큐를 비워준다.
            q.pop();
    }

    return 0;
}

 

 

결과