[Baekjoon/C++] 14940번 - 쉬운 최단거리

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

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

 

입력

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

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

 

출력

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

 

---

풀이

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

int bfs[1001][1001];
queue<pair<int, int>> q;

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

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

	int n, m;
	cin >> n >> m;

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

			if (num != 1) {
				bfs[i][j] = 0;

				if (num == 2) q.push({ i, j });
			}
			else bfs[i][j] = -1;
		}
	}

	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = curx + dx[i];
			int y = cury + dy[i];

			if (x >= 0 && x < n && y >= 0 && y < m) {
				if (bfs[x][y] == -1) {
					bfs[x][y] = bfs[curx][cury] + 1;
					q.push({ x, y });
				}
			}
		}
	}

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

	return 0;
}

 

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

			if (num != 1) {
				bfs[i][j] = 0;

				if (num == 2) q.push({ i, j });
			}
			else bfs[i][j] = -1;
		}
	}

시간 절약을 위해 입력 받을 때 result의 값도 함께 초기화해준다. 이때 num이 2나 0일 때는 bfs 순회 없이도 값을 구할 수 있기에 해당하는 칸을 미리 0으로 초기화해준다.

 

	while (!q.empty()) {
		int curx = q.front().first;
		int cury = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int x = curx + dx[i];
			int y = cury + dy[i];

			if (x >= 0 && x < n && y >= 0 && y < m) {
				if (bfs[x][y] == -1) {
					bfs[x][y] = bfs[curx][cury] + 1;
					q.push({ x, y });
				}
			}
		}
	}

너비 우선 탐색을 하는 코드이다. 탐색을 하는 부분이 문제에서 주어진 범위를 넘지 않고, 이전에 탐색을 하지 않았다면 (result가 -1이라면) 해당 칸을 탐색하고, 거리를 구한다.