[백준] 쉬운 최단거리 C++

📝 문제

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

문제

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

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

---

입력

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

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

---

출력

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

---

입출력

예제 입력

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1

예제 출력

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

---

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

void BFS(queue<pair<int, int>> q);

int iBoard[1001][1001];
int iDist[1001][1001];

int dx[4]{ 1, 0, -1, 0};
int dy[4]{ 0, 1, 0 ,-1};

int n(0), m(0);

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	queue<pair<int, int>> q;

	cin >> n >> m;

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cin >> iBoard[i][j];
			iDist[i][j] = -1;

			if (iBoard[i][j] == 2)
			{
				q.push({ i,j });
				iDist[i][j] = 0;
			}
		}
	}
	
	BFS(q);

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			if (iBoard[i][j] == 1 && iDist[i][j] == -1) // 갈 수 있는 지역이지만 도달 불가
				iDist[i][j] = -1;
			else if (iBoard[i][j] == 0 && iDist[i][j] == -1)
				iDist[i][j] = 0;
		}
	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			cout << iDist[i][j] << ' ';
		}
		cout << '\\n';
	}
	return 0;
}

void BFS(queue<pair<int, int>> q)
{
	while (!q.empty())
	{
		pair<int, int> iTemp = q.front();
		q.pop();
		for (int i = 0; i < 4; ++i)
		{
			int mx = iTemp.first + dx[i];
			int my = iTemp.second + dy[i];

			if (mx < 0 || mx >= n || my < 0 || my >= m)
				continue;

			if (iBoard[mx][my] == 0)
			{
				iDist[mx][my] = 0;
				continue;
			}

			if (iDist[mx][my] != -1)
				continue;

			q.push({ mx,my });
			iDist[mx][my] = iDist[iTemp.first][iTemp.second] + 1;
		}
	}
}

• 이 문제를 해석해 보면, 목표 지점을 기준으로 얼마만큼의 거리로 갈 수 있는지 계산하는 탐색 문제이다.

✍️ 중요 포인트

• BFS 모두 돌리고 나서, 0과 0으로 막힌 지역을 탐색해주어야 하는데, 갈 수 있지만 도달할 수 없다는 뜻은 0으로 둘러싸여 있기 때문임.