[백준/BOJ] 백준 2178번 : 미로 탐색

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

2178번: 미로 탐색

(0,0) 지점을 시작으로 (n-1, m-1) 지점을 발견할 때까지 bfs를 한다, (0,0)은 깊이(depth)가 0 이므로, (n-1, m-1)까지 지나야 하는 최소의 칸 수는 (n-1, m-1)의 깊이(depth)+1이 된다.

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <utility>
using namespace std;

int n, m;
vector<string> board;
int dx_dy[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };

int Solve()
{
	pair<int, int> start = make_pair(0, 0); //(0,0)지점부터 탐색을 시작한다
	vector<vector<bool>> discoverd(n, vector<bool>(m,false));
	vector<vector<int>> depth(n, vector<int>(m, -1));
	queue<pair<int, int>> q;

	discoverd[0][0] = true;
	depth[0][0] = 0; //시작지점의 깊이는 0
	q.push(start);

	while (!q.empty())
	{
		pair<int, int> here = q.front();
		q.pop();

		//왼쪽,오른쪽,위쪽,아래쪽 지점을 발견한다
		for (int i = 0; i < 4; i++)
		{
			pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
			
			//범위를 넘지 않고, 문자가 '1'이고, 발견되지 않는곳을 발견한다
			if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < m && board[there.first][there.second] == '1' && discoverd[there.first][there.second] == false)
			{
				//there지점을 발견했다고 체크
				discoverd[there.first][there.second] = true;

				//발견 지점의 깊이는 here 지점의 깊이+1 이다
				depth[there.first][there.second] = depth[here.first][here.second] + 1;

				//나중에 탐색할것이므로 큐에 넣는다
				q.push(there);

				//해당지점이 도착위치라면 해당 지점의 depth+1이 지나야 하는 최소 칸의 수 이다
				if (there.first == n - 1 && there.second == m - 1)
					return depth[there.first][there.second] + 1;
			}

		}
	}

	//도착위치에 도달하지  못할때
	return -1;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	cout << Solve();

	return 0;
}