[백준] 14940 쉬운 최단거리 / BFS (C++)

문제
지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력
지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력
각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

무난한 BFS 문제이다.

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

int map[1001][1001];
int dist[1001][1001];
int n, m;
int goalX, goalY;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

void BFS(int x, int y)
{
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));

	while (!q.empty())
	{
		int tmpX = q.front().first;
		int tmpY = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int xx = tmpX + dx[i];
			int yy = tmpY + dy[i];

			if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && map[xx][yy] < 100 && map[xx][yy] == 1)
			{
				q.push(make_pair(xx, yy));
				map[xx][yy] = 100;
				dist[xx][yy] = dist[tmpX][tmpY] + 1;
			}
		}	
	}	
}


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


	cin >> n >> m;


	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 2)
			{
				goalX = i;
				goalY = j;
			}
		}
	}
	// dist 초기화
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			dist[i][j] = -1;
		}
	}

	map[goalX][goalY] = 100; // 방문 표시
	dist[goalX][goalY] = 0;
	BFS(goalX, goalY);

	// 원래 못가는 곳 체크 - 처음에 dist를 -1 로 초기화해두었기 때문에 다시 채워준다.
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			if (map[i][j] == 0)
			{
				dist[i][j] = 0;
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cout << dist[i][j] << " ";
		}
		cout << "\n";
	}

	return 0;
}