[백준]7562번: 나이트의 이동 / BFS 최단경로

BFS를 이용하여 시작한 정점(x,y)에서 목표점까지 (X,Y) 도달 가능한 최단경로를 구하는 문제이다.

도달할 수 없는 경우를 체크하여 갈 수 없다면 0을 출력하고,  depth[xx][yy] = depth[x_temp][y_temp] + 1;

를 통해서 갈 수 있는 depth를 구한다. (x_temp,y_temp) -> (xx,yy) 로 갈  수 있다면 깊이를 +1 한다.

https://www.acmicpc.net/problem/7562 

#include<iostream>

using namespace std;

#include<queue>

#include<cstring>

int l, test;

int map[301][301];

int depth[301][301];

int cnt;

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

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

int visit[301][301];

queue <int> qx;

queue <int> qy;

int a, b, c, d;

bool break_ok = false;

bool checkOk(int x,int y)

{

if (x >= 0 && y >= 0 && x < l && y <l)

return true;

else return false;

}

void bfs()

{

qx.push(a);

qy.push(b);

visit[a][b] = true;

cnt = 0, break_ok=false;

int x_temp, y_temp;

while (!qx.empty() && !qy.empty())

{

x_temp = qx.front(); qx.pop();

y_temp = qy.front(); qy.pop();

if (x_temp == c && y_temp == d)

{

cout <<depth[x_temp][y_temp] << endl;

break_ok = true;

break;

}

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

{

int xx = x_temp + dx[i];

int yy = y_temp + dy[i];

if (checkOk(xx, yy) && !visit[xx][yy])

{

visit[xx][yy] = true;

qx.push(xx);

qy.push(yy);

depth[xx][yy] = depth[x_temp][y_temp] + 1;

}

}

}

}

int main()

{

cin >> test;

while (test--)

{

cin >> l;

cin >> a >> b;

cin >> c >> d;

map[a][b] = 1;

map[c][d] = 1;

bfs();

if (!break_ok)

cout << 0 << endl; //갈수 없을 경우 

memset(map, 0, sizeof(map));

memset(visit, 0, sizeof(visit));

memset(depth, 0, sizeof(depth));

while (!qx.empty())

qx.pop();

while (!qy.empty())

qy.pop();

}

return 0;

}