[백준 2178] 미로 탐색 (BFS)

문제출처: https://www.acmicpc.net/problem/2178

풀이

최단거리구하기. 즉 dfs가 아닌 bfs를 사용해야합니다.  저는 방문 배열을 선언하여 0을 방문하지않았을 때를 의미하고 그외에 모든 양수값은 방문처리가 되었을때, 그리고 동시에 그값이 최단거리(칸)을 의미하게 함으로써 check[n-1][m-1]이 답이 될 수 있게끔 로직을 구성했습니다. 

1. map을 입력받습니다.

2. 0,0좌표를 시작으로 bfs를 돌립니다. 주위에 길이있고 방문하지않은 좌표를 최단칸으로 갱신합니다.(check배열로 갱신)

3. 최종적으로 check[n-1][m-1]은 0,0좌표부터 현재의 좌표까지의(답) 최단칸수입니다.

코드

#include<iostream>
#include<queue>
using namespace std;
char map[100][100];
int check[100][100];
int dx[4] = { 0,0,1,-1 };
int dy[4] = { -1,1,0,0 };
int n, m;
void bfs(int y, int x);
int main()
{
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	//시작위치가 정해져있으므로 바로 bfs!
	bfs(0, 0);
	//15행 선언후 아래 행 먼저선언하자(어짜피 머릿속으로 이렇게 계산하자고생각했으므로)
	//check배열에 0,0부터 현재좌표까지의 최단칸수담음
	cout << check[n - 1][m - 1] << endl;
}
void bfs(int y,int x)
{
	queue<pair<int, int>>q;
	q.push({ y,x });
	check[y][x] = 1;
	while (!q.empty())
	{
		x=q.front().second;
		y=q.front().first;
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && nx < m && ny < n)
			{
				//길이있고, 방문하지않았으면 방문 및 최단거리 갱신
				if (map[ny][nx] == '1' && check[ny][nx] == 0)
				{
					q.push({ ny,nx });
					check[ny][nx] = check[y][x] + 1;
				}
			}
		}
	}
}

결과