백준 2178 C++ - 미로 탐색

Intro

문제해결 및 소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#define MAX 101

using namespace std;

/*									<문제해결>
				규칙1. 미로에서 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸이다.
				규칙2. 상하좌우로만 이동할 수 있음.

				문제를 풀기위해서는 DFS 또는 BFS 알고리즘을 활용해야한다. 하지만 DFS알고리즘을 사용할 경우,
				최적의 해를 구할 수 없을수도있으므로 이런 최단경로를 묻는 문제는 BFS알고리즘을 사용한다.

                예제1) maze[4][6]
				---- +y ---->
			|	1 0 1 1 1 1		    (0,0)에서 탐색을 시작하여, 상하좌우순으로 다음칸을 탐색한다. 
			+x	1 0 1 0 1 0 		다음칸이 탐색이 가능한 곳이라면(방문x, 1이 있는 칸) 현재칸의
			|	1 0 1 0 1 1         count에서 +1 한다.
			v	1 1 1 0 1 1 

                count[4][6]     
                1 0 9 10 11 12      알고리즘을 돌며 count배열을 채워나간다면 왼쪽같이 채워질것이다.
                2 0 8 0  12 0       
                3 0 7 0  13 14      최종적으로 가장오른쪽아래의 값을 출력해주면된다.
                4 5 6 0  14 15

*/


vector<int> maze[MAX];		// 미로
bool visited[MAX][MAX];		// 방문여부
int cnt[MAX][MAX];			// 해당좌표까지 가는데 이동해야할 최소 칸 수

// 상하좌우
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

int N, M;

void BFS(int x, int y)
{
	queue<pair<int,int>> que;
	que.push(pair<int,int>(x,y));		// .. (0,0)부터 탐색시작
	visited[x][y] = true;
	
	cnt[x][y]++;

	while (!que.empty())
	{
		int a = que.front().first;		// ..  현재칸의 x좌표
		int b = que.front().second;		// .. 현재칸의 y좌표
		que.pop();

		// 상하좌우 순서로 탐색
		for (int i = 0;i < 4;i++)
		{
			int nx = a + dx[i];
			int ny = b + dy[i];

			// 미로범위 벗어난 탐색은 무시
			if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

			// 방문하지않았고, 이동할 수 있는 칸일경우
			if (!visited[nx][ny] && maze[nx][ny] == 1)
			{
				visited[nx][ny] = true;
				que.push(pair<int, int>(nx, ny));
				cnt[nx][ny] = cnt[a][b] + 1;
			}
		}
	}
}

int main()
{
	cin >> N >> M;

	// 간선입력
	for (int i = 0;i < N;i++)
	{
		string input;
		cin >> input;

		for (unsigned int j = 0;j < input.length();j++)
		{
			if (input[j] == '0') maze[i].push_back(0);
			else maze[i].push_back(1);
		}
	}

	BFS(0, 0);

	// 목표좌표까지 가는데 이동해야할 최소 칸 수
	cout << cnt[N - 1][M - 1];
}