[백준 / C++ ] 14940 최단거리 - BFS

백준 14940번 최단거리

문제

 

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

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

입력

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

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

출력

 

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

예제 입력 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

예제 출력 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

---

 

14940 쉬운 최단거리 문제 풀이

 

이 문제는 간단하게 BFS로 거리를 파악할 수 있는 문제이다.

 

세로 N과 가로 M의 숫자를 입력 받았을 때, 2의 위치를 파악하여 그 위치로 부터 각 지점이 얼마나 떨어져있는지 확인하면 된다. 여기서 주의할 점은, 가지 못하는 지점은 -1로 출력해야한다는 점이다.

 

BFS 코드

 

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

int num[1001][1001];
bool check[1001][1001] = { 0, };

queue<pair<int,int>> que;
int dx[4] = {-1 , 0, 1, 0};
int dy[4] = {0, 1, 0 , -1};

int main() {
	int n, m;
	cin >> n >> m;
	int x, y;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> num[i][j];

			if (num[i][j] == 2) {
				y = i;
				x = j;
			}
		}
	}
	//cout << " X : " << x << " Y : " << y << '\n';

	que.push({ x,y });
	check[y][x] = 1;
	num[y][x] = 0;

	while (!que.empty()) {
		pair<int, int> que_xy = que.front();
		que.pop();

		

		for (int i = 0; i < 4; i++) {

			int num_x = que_xy.first + dx[i];
			int num_y = que_xy.second + dy[i];

			if (num_x >= 0 && num_y >= 0 && num_x < m && num_y < n) {
				if (check[num_y][num_x] == 0 && num[num_y][num_x] != 0) {
					num[num_y][num_x] = num[que_xy.second][que_xy.first] + 1;
					check[num_y][num_x] = 1;
					que.push({ num_x,num_y });
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (num[i][j] == 1 && check[i][j] == 0) {
				num[i][j] = -1;
			}
			cout << num[i][j]<< " ";

		}
		cout << '\n';
	}
	return 0;

}