백준 - 2178 미로탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

본 문제의 요구사항은 출발지점에서 도착지점으로 가는 최소 경로를 찾는 문제이며 BFS 방식으로 풀면 쉽게 해결될 수있다. 알고리즘은 아래와 같다

1. 큐를 만들고 출발지점값을 1로 세팅 ( 첫칸 방문 )

2. 갈수 있는 인접 지점을 선택 해당 값을 이전값 +1 로 세팅 한다.

3. 2단계에서 선택된 각 인접 지점들에 대해서 2단계를 반복한다.

4. 선택된 지점이 도착된 값이 되면 그점의 값이 최소 경로 값이 된다.

 

이를 코드로 구현하면 아래와 같다.

 

 

 

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main()
{
	int row, col;

	cin >> row >> col;

	vector<vector<int>> m(row, vector<int>(col, 0));
	for (int r = 0; r < row; r++)
	{
		string tmp;
		cin >> tmp;
		for (int c = 0; c < col; c++)
		{
			m[r][c] = (tmp[c]-'0') * -1;
		}
	}

	queue<pair<int, int>> q;

	q.push(make_pair(0, 0));

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

	m[0][0] = 1;

	while (!q.empty())
	{
		auto p = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextR = p.first + nextTable[i][0];
			int nextC = p.second + nextTable[i][1];

			if (nextR < 0 || nextR >= row) continue;
			if (nextC < 0 || nextC >= col) continue;

			if (nextR == row - 1 && nextC == col - 1)
			{
				cout << m[p.first][p.second] + 1 << endl;
				return 0;
			}
			if (m[nextR][nextC] == 0) continue;
			int nextVal = m[p.first][p.second] + 1;
			if (m[nextR][nextC] == -1 || m[nextR][nextC] > nextVal)
			{
				m[nextR][nextC] = nextVal;
				q.push(make_pair(nextR, nextC));
			}
		}
	}
	return 0;

}