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

문제

 

 

시행 착오

DFS 로 풀이하려다 시간 초과가 났다. 잘 생각해보니 DFS보단 BFS 가 훨씬 효율적이고 정확한 듯 해서 바꾸어서 풀었다.

 

 

해결 방법

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

int N, M;

int arr[100][100];
int num[100][100];
bool visited[100][100] = {false};

queue < pair<int,int> > q;

int x_dir[4] = { -1 , 1 , 0 , 0 };
int y_dir[4] = { 0 , 0 , -1 , 1 };

void bfs(int y, int x)
{
	visited[y][x] = true;

	q.push(make_pair(y, x));

	num[y][x]++;

	while (!q.empty())
	{
		int y = q.front().first;
		int x = q.front().second;
		
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int ny = y + y_dir[i];
			int nx = x + x_dir[i];


			if ((ny >= 0 && ny < N) && (nx >= 0 && nx < M)
				&& !visited[ny][nx] && arr[ny][nx] == 1)
			{
				q.push(make_pair(ny, nx));

				visited[ny][nx] = true;

				num[ny][nx] = num[y][x] + 1;

			}

		}
	}
}

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

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1d", &arr[i][j]);
		}
	}
	
	bfs(0, 0);

	cout << num[N-1][M-1];

	return 0;
}