백준14940 - 쉬운 최단거리

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

14940번: 쉬운 최단거리

다익스트라를 이용한 문제다. 벽인 경우는 0을 출력하고 갈 수 있는 곳이지만 도달할 수 없는 경우는 -1을 출력한다. 그 외의 다른 구역은 출발점에서 도달 가능한 최소비용을 출력한다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
#define MAX 1001
using namespace std;

int n, m; //좌표 크기 n X m
int x, y; //출발점 (x, y)
int mat[MAX][MAX]; //좌표 정보
int d[MAX][MAX]; //다익스트라 결과를 저장할 공간

//상하좌우
int dx[] = { 1,-1,0,0 };
int dy[] = { 0,0,1,-1 };

void dijkstra(int x, int y) {
	queue<pair<int, int>> q;
	q.push(pair<int, int>(x, y));
	d[x][y] = 0;

	while (!q.empty()) {
		//큐에 첫번째 원소 추출하고 삭제
		x = q.front().first;
		y = q.front().second;
		q.pop();

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

			if (1 <= nx && nx <= n && 1 <= ny && ny <= m) { //유효범위이면	
				if (mat[nx][ny] == 1 && d[nx][ny] > d[x][y] + 1) { //빈 공간이고 전에 있던 비용보다 갱신할 비용이 더 작으면
					q.push(pair<int, int>(nx, ny)); //큐에 다음에 이동할 공간을 넣어주고
					d[nx][ny] = d[x][y] + 1; //비용을 갱신
				}
			}
		}
	}
}

int main() {
	scanf("%d %d", &n, &m);

	//다익스트라를 수행하기 전 모든 공간을 987654321로 세팅
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			d[i][j] = 987654321;
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			scanf("%d", &mat[i][j]);
			if (mat[i][j] == 2) { //출발점이면 위치를 기억
				x = i;
				y = j;
			}
		}
	}

	dijkstra(x, y);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (mat[i][j] == 0) { //벽이면
				printf("0 "); //0출력
			}
			else if (mat[i][j] == 1 && d[i][j] == 987654321) { //빈 공간이고 갈 수 없는 공간이면
				printf("-1 "); //-1출력
			}
			else { //그 외의 공간이면
				printf("%d ", d[i][j]); //최소 비용을 출력
			}
		}
		printf("\n");
	}
}