[C/C++] 백준 - 14940번 : 쉬운 최단거리

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

14940번: 쉬운 최단거리

문제

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

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

입력

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

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

출력

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

 

문제 난이도는 Gold5라고 되어있는데 어렵지 않은 문제이다.

BFS로 갈 수 있는 지점에 대해서 거리를 최신화시켜주면 되는데, 원래 갈 수 없는 땅인데 못가는 곳과, 원래

갈 수 있는 곳이지만 도달하지 못한 곳 분류만 잘 해주면 되는 문제이다.

 

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <bitset>

using namespace std;

int N, M;
int adj[1003][1003];
int board[1003][1003];
int visited[1003][1003];
queue<pair<int,int>> q;

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

int isValid(int y, int x) {
	return (0 <= y && y < N && 0 <= x && x < M);
}

void Input_Data() {
	cin >> N >> M;
	memset(board, -1, sizeof(board));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> adj[i][j];
			if (adj[i][j] == 2) {
				q.push({ i,j });
				visited[i][j] = 0;
				board[i][j] = 0;
			}
			else if (adj[i][j] == 0) board[i][j] = 0;
		}
	}
}

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

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

			if (!isValid(ny, nx)) continue;
			if (!visited[ny][nx] && adj[ny][nx] == 1) {
				visited[ny][nx] = visited[y][x] + 1;
				q.push({ ny, nx });
			}
		}
	}
}

void Print() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (board[i][j] == -1)
				if (visited[i][j] == 0)
					cout << -1 << " ";
				else
					cout << visited[i][j] << " ";
			else
				cout << 0 << " ";
			
		}
		cout << endl;
	}
}

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

	Input_Data();
	BFS();
	Print();
	
	return 0;
}