백준 14940 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

- 간단한 그래프 탐색 문제이다. 시간복잡도는 한 번의 bfs가 실행되므로 O(MN)

 

- M과 N이 최대 1000이므로, 모든 칸에 대해서 bfs를 실행한다면 시간초과가 나게 된다. 따라서, 좌표가 2인 칸에서만 bfs를 실행 해 주면 된다. map과 똑같은 크기의 answer배열에 정답을 넣어줄 것이다.

 

- 탐색을 진행할 때 방문하는 노드의 기준은

 

1. visit했는가?

2. map이 갈 수 없는(0) 곳인가?

3. 범위를 벗어나는가?

 

이다. 또, 큐에 넣기 전에 현재 now값의 +1을 넣어주는 것과 answer[nx][ny]에 now+1값을 넣어주는 것도 중요하다.

 

- bfs를 마치면, 출력을 시작하는데 이 때 갈 수 있는 곳이면서 방문하지 못한 곳을 -1로 표시하는 작업을 진행한다. 그러한 곳은 간단하게 visited[x][y]가 false이고, map[x][y]가 0이 아니면 된다. 그러한 부분은 -1로 고쳐주고, 출력을 진행한다.

 

 

#include <iostream>
#include <queue>
using namespace std;
int n,m;
int map[1000][1000];
int answer[1000][1000];
bool visited[1000][1000];
int dx[] = { 0,0,1,-1 };
int dy[] = { -1,1,0,0 };
void bfs(int x, int y) {
	int now = 0;
	visited[x][y] = true;
	queue<pair<pair<int, int>, int>> q;
	q.push({ {x,y}, now });
	while (!q.empty()){
		int tx = q.front().first.first;
		int ty = q.front().first.second;
		now = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++) {
			int nx = tx + dx[k];
			int ny = ty + dy[k];
			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (visited[nx][ny] || map[nx][ny] == 0) continue;
			visited[nx][ny] = true;
			answer[nx][ny] = now+1;
			q.push({ { nx, ny }, now + 1 });
		}
	}
}
int main() {
	ios_base::sync_with_stdio;
	cin.tie(NULL);
	int start_x = 0; int start_y = 0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2) {
				start_x = i; start_y = j;
			}
		}
	}
	bfs(start_x, start_y);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!visited[i][j] && map[i][j] != 0) answer[i][j] = -1;
			cout << answer[i][j] << " ";
		}
		cout << '\n';
	}
	return 0;
}