[백준] 2178번 미로 탐색

문제 링크

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

 

로직이 분명히 문제가 없는데 틀렸다고 나오는 게 이해가 안 됐다. 알고 보니 경계 문제였다. 경계는 늘 문제구만. 거리 계산하는 부분을 별도로 배열로 관리하면 채점 상에 나오는 메모리가 (40kb) 정도 절약되지만, 큐를 통해 한 번에 관리하는 게 나는 더 편하다. 처음에는 DFS로 풀어보려다 복잡해질 것 같아 BFS로 거리 계산을 해보려고 하니까 금방 됐다. 경계만 아니었다면..

 

#include <iostream>
#include <queue>
using namespace std;

queue<pair<pair<int, int>, int>> q;
int N, M;
int map[102][102];
bool visited[102][102];
int dist[102][102];
int dir_n[] = { 1, 0, -1, 0 };
int dir_m[] = { 0, 1, 0, -1 };

void bfs(int n, int m);

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

	for (int n = 1; n <= N; ++n)
	{
		string line;
		cin >> line;
		for (int m = 1; m <= M; ++m)
		{
			int number = line[m - 1] - '0';
			map[n][m] = number;
		}
	}
	
	bfs(1, 1);
}

void bfs(int n, int m)
{
	q.push({ { n, m }, 1 });

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

		auto [current_n, current_m] = node.first;
		int current_count = node.second;		
		visited[current_n][current_m] = true;

		if (current_n == N && current_m == M)
		{
			cout << current_count;
			return;
		}

		for (int i = 0; i < 4; ++i)
		{
			int next_dir_n = dir_n[i] + current_n;
			int next_dir_m = dir_m[i] + current_m;

			if (map[next_dir_n][next_dir_m] && false == visited[next_dir_n][next_dir_m])
			{
				visited[next_dir_n][next_dir_m] = true;
				q.push({ { next_dir_n, next_dir_m }, current_count + 1 });
			}
		}
	}
}