14940번 - 쉬운 최단거리

1. 문제

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

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

2. 입력

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

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

3. 출력

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

4. 풀이

1) 입력이 2인 지점을 초기 위치로 설정

2) BFS를 통해 초기 위치로 부터 최단 거리 구하기

• BFS로 초기 위치로부터 탐색해가면서 최단 거리 저장

3) 도달할 수 없는 위치는 -1로 출력하기

• 입력 시 2와 0인 위치는 이미 방문한 것으로 설정하고 너비 우선 탐색
• 출력 시 방문하지 않은 곳을 -1로 출력하기

5. 소스코드 with C++

#include<iostream>
#include<queue>

using namespace std;

int map[1001][1001]; // 최단 거리 저장
int input[1001][1001]; // 입력시 0과 2 확인
bool visit[1001][1001]; // 방문했는지 확인

int dx[4] = { 1,-1,0,0 }; // 가로
int dy[4] = { 0,0,1,-1 }; // 세로

queue<pair<int, int>> q;
int n, m; // 입력받는 가로, 세로 크기

void bfs() {
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
				if (visit[nx][ny] == false) {
					map[nx][ny] = map[x][y] + 1;
					visit[nx][ny] = true;
					q.push({ nx,ny }); // 인접한 가로 세로를 큐에 삽입
				}
			}
		}
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie();

	cin >> n >> m; // 가로 세로 입력
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> input[i][j]; // 0과 2 확인을 위해 입력 값 저장
			if (input[i][j] == 2) { // 2일 경우
				map[i][j] = 0; // 초기 위치로 설정
				visit[i][j] = true; // 방문한 것으로 설정
				q.push({ i,j }); // 맨 처음 큐에 삽입
			}
			else if (input[i][j] == 0) { // 0일 경우
				visit[i][j] = true; // 1로 입력 된 곳에서 갈 수 없을 경우 -1 출력이므로 0 입력은 방문한 것으로 설정
			}
		}
	}

	bfs(); // 너비 우선 탐색을 통해 최단 거리 구하기

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (visit[i][j] == false) {
				printf("-1 "); // 갈 수 없는 곳 -1 출력
			}
			else
				printf("%d ", map[i][j]); // 최단 거리 출력
		}
		printf("\\n");
	}

	return 0;
}