[백준 C++] 14940 쉬운 최단거리 - 너비우선탐색

14940번: 쉬운 최단거리

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

int N, M;
int Map[1000][1000];
int Distance[1000][1000];
queue<pair<int, int>> SearchQueue;

void BFS(int StartRow, int StartCol)
{
	SearchQueue.emplace(StartRow, StartCol);

	while (!SearchQueue.empty())
	{
		int CurRow = SearchQueue.front().first;
		int CurCol = SearchQueue.front().second;
		SearchQueue.pop();

		if (Map[CurRow][CurCol] == 0)
		{
			continue;
		}

		int CurDistance = Distance[CurRow][CurCol];
		Map[CurRow][CurCol] = 0;

		// Left
		if (CurCol > 0
			&& Map[CurRow][CurCol - 1] != 0)
		{
			Distance[CurRow][CurCol - 1] = CurDistance + 1;
			SearchQueue.emplace(CurRow, CurCol - 1);
		}

		// Top
		if (CurRow > 0
			&& Map[CurRow - 1][CurCol] != 0)
		{
			Distance[CurRow - 1][CurCol] = CurDistance + 1;
			SearchQueue.emplace(CurRow - 1, CurCol);
		}

		// Right
		if (CurCol < M - 1
			&& Map[CurRow][CurCol + 1] != 0)
		{
			Distance[CurRow][CurCol + 1] = CurDistance + 1;
			SearchQueue.emplace(CurRow, CurCol + 1);
		}

		// Bottom
		if (CurRow < N - 1
			&& Map[CurRow + 1][CurCol] != 0)
		{
			Distance[CurRow + 1][CurCol] = CurDistance + 1;
			SearchQueue.emplace(CurRow + 1, CurCol);
		}
	}
}

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

	int StartRow = 0, StartCol = 0;

	cin >> N >> M;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> Map[i][j];

			if (Map[i][j] == 2)
			{
				StartRow = i;
				StartCol = j;
			}
		}
	}

	BFS(StartRow, StartCol);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			if (Map[i][j] == 1)
			{
				cout << -1 << ' ';
			}
			else
			{
				cout << Distance[i][j] << ' ';
			}
		}
		cout << '\n';
	}
}

---

 

너비 우선 탐색을 이용해서 목적지에서부터 모든 노드까지 각 깊이를 체크해주어 푸는 문제입니다.

이미 탐색된 노드는 다시 갈 수 없는 땅이므로 값을 0으로 바꿔주고

BFS가 완료된 시점에서 값이 1인 노드는 목적지로부터 도달할 수 없는 위치로써 -1을 출력하도록 했습니다.