[백준]: 2178번: 미로탐색 / BFS depth구하기(최단경로)

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

해당 문제는 (1, 1) /start -> <N,M) / end로 경로이동시에 최단경로를 구하는 문제이다.

해당 문제는 bfs의 depth를 구하면 최단경로를 구할 수 있다.

기존의 bfs를 수행하면서 depth를 누적하면서 구하면 된다. 따로 Max, min algorithm stl을 쓸 필요없이 (1,1) -> (n,m) 까지 순차적으로 depth를 구하는

것이기 때문에 그대로 bfs를 수행하면서 depth를 누적하면 해결된다.

#include<iostream>

using namespace std;

#include<algorithm>

#include<cstring>

#include<queue>

queue <int> qx;

queue <int> qy;

int n, m, miro[200][200];

int xx[4] = { 0,-1,0,1 };

int yy[4] = { 1,0,-1,0 };

bool visited[200][200];

int depth[200][200];

void bfs(int x, int y)

{

if (x <= 0 && y <= 0) return;

visited[x][y] = true;

qx.push(x);

qy.push(y);

int temp_x, temp_y;

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

{

temp_x = qx.front();

temp_y = qy.front();

qx.pop(); qy.pop();

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

{

int nx = temp_x + xx[i];

int ny = temp_y + yy[i];

if (miro[nx][ny] && nx <= n && ny <= m && !visited[nx][ny])

{

visited[nx][ny] = true;

qx.push(nx);

qy.push(ny);

depth[nx][ny] = depth[temp_x][temp_y] + 1;

}

}

}

}

int main()

{

cin >> n >> m;

for (int i = 1; i <= n; i++)

{

for (int j = 1; j <= m; j++)

{

scanf("%1d", &miro[i][j]);

}

}

depth[1][1] = 1;

bfs(1, 1);

cout << depth[n][m] << "\n";

return 0;

}