[Silver 1] 14940번 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

이 문제는 BFS를 통해 해결할 수 있다.

문제에서 "원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 라는

규칙이 있다. 이 규칙을 통해 문제를 풀기 위해 result라는 배열을 생성하고 memset을 통해 -1로 초기화 해주었다.

순회 후 graph가 원래 0인 부분은 0으로 출력하고 이외에는 result 배열을 출력함으로써 조건을 만족하였다.

 

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

int graph[1001][1001] = {0,};
int visited[1001][1001] = { 0, };
int result[1001][1001] = { 0, };
int N, M;
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
queue<pair<int, int>> q;

void bfs(int x,int y) {
	q.push(make_pair(y, x));
	result[y][x] = 0;
	visited[y][x] = 1;
	while (!q.empty()) {
		int ry = q.front().first;
		int rx = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int ux = rx + dx[i], uy = ry + dy[i];
			if (ux <0 || uy<0 || ux>M || uy>N) continue;

			if (graph[uy][ux] == 0) continue;

			if (!visited[uy][ux]) {
				q.push(make_pair(uy, ux));
				result[uy][ux] = result[ry][rx] + 1;
				visited[uy][ux] = 1;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> M;
	int x = 0, y = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			int value;
			cin >> value;
			graph[i][j] = value;
			if (value == 2) {
				y = i;
				x = j;
			}
			
		}
	}
	memset(result, -1, sizeof(result));
	bfs(x, y);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (graph[i][j] == 0) cout << graph[i][j] << ' ';
			else cout << result[i][j]<<' ';
		}
		cout << '\n';
	}
}