[백준 / BOJ] C++ 2178 미로 탐색

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

2178번: 미로 탐색

 

풀이

연결된 점을 찾아가는 문제이다. (N,M). 이런문제는 알고리즘 분류에도 나와있지만, 너비 우선탐색으로 풀 수있다.

너비우선 탐색은 보통 큐 (queue)를 이용하여 구현한다.

 

큐에 관해 포스팅 되어있으니 참고하길 바란다.

https://hyun-jun5.tistory.com/m/57

[Algorithm] C++ Queue (큐) 클래스 구현

비슷한 백준 문제로는, DFS와 BFS 문제가 있다.

https://hyun-jun5.tistory.com/m/56

[백준 / BOJ] C++ 1260 DFS와 BFS

 

일단 이동하기 위해 입력한 문자열 값의 index에 1이 들어있어야만 이동하여야하고, 해당 index에서 상, 하, 좌, 우 로만 

이동을 하여야한다. 이 점을 유의하여, 문제를 풀면된다.

 

항상 (1,1)의 위치에서 시작을 하여야하기에, 출발 위치를 기준으로 큐에 넣어주고, 그 위치를 변수에 저장한 후 

저장된 문자열의 index를 하나씩 탐색하여 문제를 푼다.

 

Code

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

using namespace std;
int N, M;

string maze[100];
int _search[100][100];
int _isVisit[100][100];

int BFS(int X, int Y)
{
	queue<pair<int, int>> q;
	int move[4][2] = { {0,1},{0,-1}, {1,0}, {-1,0} };

	// 시작점 입력
	q.push({ 1, 1 });

	while (!q.empty())
	{
		X = q.front().first;
		Y = q.front().second;

		q.pop();

		// 4방향 탐색
		for (int i = 0; i < 4; i++)
		{
			int SearchX = X + move[i][0];
			int SearchY = Y + move[i][1];

			if (SearchX < 101 && SearchY < 101 && _search[SearchX][SearchY] && !_isVisit[SearchX][SearchY])
			{
				q.push({ SearchX,SearchY });
				_isVisit[SearchX][SearchY] = _isVisit[X][Y] + 1;
			}
		}
	}
	return _isVisit[N][M];
}

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

	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		cin >> maze[i];
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (maze[i][j] == '1')
				// 1,1에서 시작하기에, 좌표에 + 1을 시켜준다.
				_search[i + 1][j + 1] = 1;
		}
	}

	//처음 방문 좌표 1,1은 탐색한거로 간주
	_isVisit[1][1] = 1;
	cout << BFS(1, 1) << "\n";
}