[백준 알고리즘][BFS] 7562번 나이트의 이동

문제

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

입력과 출력

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

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

풀이 

방금 풀었던 미로탐색과 비슷한 문제다 근데 대신 미로에선 상하좌우 4곳으로 뻗어나갈 수 있지만 여기서는 총 8곳으로 뻗어나갈 수 있다

이것도 마찬가지로 한번 큐가 돌때 갈 수 있는 사이즈를 체크하고 그 사이즈만큼 큐에서 pop되고나면 한단계가 지난 것이고 몇단계를 거쳐야 목적지에 도착할 수 있는지를 찾는 문제인것같다

미로랑 똑같이 풀었는데 테스트케이스조차 맞추지 못한다 ㅠㅠ 이유를 모르겠다..

-> 배열 dx, dy를 잘못초기화해서 문제였다 ㅠㅠ 

* 한번에 맞았당 ㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎㅎ

코드

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

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

int BFS(int a, int b) //a, b는 출발점 좌표

{

int i, qsize, level=0;

struct point tmp;

tmp.x=a;

tmp.y=b;

chess[a][b]=true;

Q.push(tmp);

while(Q.empty()!=true)

{

qsize=Q.size();

for(i=0; i<qsize; i++){

tmp=Q.front();

Q.pop();

if(tmp.x == n && tmp.y == m){

return level;

}

visit(tmp);

}

level++;

}

return level;

}

void visit(struct point tmp)

{

int i;

struct point item;

for(i=0; i<8; i++)

{

if(tmp.x + dx[i]< 0 || tmp.x + dx[i] >= L

|| tmp.y + dy[i] < 0 || tmp.y + dy[i]>= L)

continue;

if(chess[tmp.x+dx[i]][tmp.y+dy[i]] !=true)

{

chess[tmp.x+dx[i]][tmp.y+dy[i]] =true;

item.x = tmp.x+dx[i];

item.y = tmp.y+dy[i];

Q.push(item);

}

}

}