[백준 18404번] 현명한 나이트 (C++)

문제링크 : https://www.acmicpc.net/problem/18404

18404번: 현명한 나이트

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, M, X, Y, A, B;
int dx[] = {-2,-2,-1,-1, 1,1, 2,2}; //나이트 이동 방향
int dy[] = {-1, 1,-2, 2,-2,2,-1,1};
int visited[501][501];
int arr[501][501];
queue<pii>q;

void bfs(int y, int x)
{
    arr[y][x]=0;
    visited[y][x]=1;
    q.push({y, x});

    while(!q.empty())
    {
        auto[yy, xx] = q.front(); 
        q.pop();

        for(int i=0; i<8; i++)
        {
            int ny = yy+dy[i];
            int nx = xx+dx[i];

            if(ny<=0 || nx<=0 || ny>N || nx>N) continue;
            if(visited[ny][nx]) continue;
            visited[ny][nx]=1;
            arr[ny][nx] = arr[yy][xx]+1; //거리증가
            q.push({ny, nx});
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N >> M;
    cin >> X >> Y;
    for(int i=0; i<M; i++)
    {
        cin >> A >> B;
        bfs(X, Y); //현재위치기준 bfs 탐색
        cout << arr[A][B] << " "; //입력받은 상대말의 위치
    }

    return 0;
}

 

동서남북으로 움직이는 기본적인 bfs문제에서 이동방향을 살짝 바꾼 bfs 문제이다.

체스의 이동방식에 맞게 이동방향 값을 설정해준다 (dx, dy배열)

 

이후 bfs 탐색을 돌릴때 증가하는 거리수치를 저장할 배열 하나를 추가하여 큐에 다음값을 넘길때 거리가 하나 증가되도록 해준다.

이후 입력받은 상대말의 위치인 arr[A][B]를 출력해주면 된다.

 

bfs 탐색을 할 때 한번에 각 위치에 대한 거리값을 모두 저장하므로, bfs 자체는 1번만 돌려주면 된다.

이후 입력받은 A, B에 대해 해당 위치에 대한 거리값이 담긴 arr[A][B]를 바로 출력해주면 된다.