[PS] 백준 7562번: 나이트의 이동

|

문제

내가 이해한 문제 내용

나이트가 8방향으로 갈 수 있고 출발지점과 도착지점이 주어질 때 몇번만에 갈 수 있는지 구하시오.

접근 방식

BFS로 8방향 체크하면서 푸는 전형적인 문제.

어려웠던 점 & 배운 점

BFS 큐에서 빠져나왔을 때 큐가 초기화되지 않은 점을 고려하지 못했음.

시간복잡도

8방향이 정해져있지만 2차원 배열의 크기에 비례하기 때문에 $O(N^2)$

코드

#include <cstdio>
#include <cstring>
#include <queue>

struct coor{
    int x;
    int y;
    int move;
};

int chess[301][301],visit[301][301];
int tc,size,s1,s2,e1,e2;
std::queue<coor> q;

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


int bfs(int s1, int s2)
{
    q.push({s1,s2,0});
    visit[s1][s2]=1;

    int ans = 0;
    while(!q.empty()){
        coor cur = q.front(); q.pop();
        ans = cur.move;
        if(cur.x==e1 && cur.y==e2)  break;
        for(int i=0; i<8; i++){
            int _x = cur.x + dx[i];
            int _y = cur.y + dy[i];

            if(_x<0 || _x>=size || _y<0 || _y>=size) continue;
            if(!visit[_x][_y]){
                visit[_x][_y] = 1;
                q.push({_x,_y,ans+1});
            }
        }
    }
    return ans;
}

int main(void)
{
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&size);
        scanf("%d%d",&s1,&s2);
        scanf("%d%d",&e1,&e2);
        printf("%d\n",bfs(s1,s2));
        memset(visit,0,sizeof(visit));
        while(!q.empty()) q.pop();
    }
    return 0;
}