백준2665 미로 만들기

작성일 | In

문제 링크

  • http://icpc.me/2665

문제 출처

  • 1997 전국 본선 고등부2

사용 알고리즘

  • Dijkstra
  • 0-1 BFS

시간복잡도

  • O(N2)

풀이

각 셀을 정점으로 잡고, 인접한 셀끼리 간선으로 이어줍시다. 그러면 정점 N2개, 간선 O(N2)로 구성된 그래프가 만들어집니다.
이때, 도착 정점이 흰 방이라면 해당 간선의 가중치를 0, 검은 방이라면 1로 설정해주어야 합니다.

(1, 1)부터 (N, N)까지 갈 때 검은 방을 최소 몇 개를 거쳐야 하는지를 물어본다는 것은, 위에서 모델링 한 그래프에서 최단 거리를 묻는 것과 같습니다.
Dijkstra 알고리즘을 이용해 구할 수 있습니다. 하지만 간선의 가중치가 0 또는 1이므로 (이 글)에서 설명한 0-1 BFS를 이용하면 O(V + E)만에 최단 거리를 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

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

int arr[55][55];
int dist[2525];
int n;

inline int convert(int i, int j){
	return n*(i-1)+j;
}

inline bool out(int i, int j){
	return i <= 0 || i > n || j <= 0 || j > n;
}

int main(){
	scanf("%d", &n);
	for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) scanf("%1d", &arr[i][j]);
	memset(dist, 0x3f, sizeof dist);

	dist[convert(1, 1)] = 0;
	deque<p> dq; dq.push_back({1, 1});
	while(!dq.empty()){
		int nowX = dq.front().x;
		int nowY = dq.front().y;
		int now = convert(nowX, nowY);
		dq.pop_front();

		for(int k=0; k<4; k++){
			int nxtX = nowX + dx[k];
			int nxtY = nowY + dy[k];
			int nxt = convert(nxtX, nxtY);
			if(out(nxtX, nxtY)) continue;
			int cost = arr[nxtX][nxtY] ? 0 : 1;
			if(dist[nxt] > dist[now] + cost){
				dist[nxt] = dist[now] + cost;
				if(cost == 1) dq.push_back({nxtX, nxtY});
				else dq.push_front({nxtX, nxtY});
			}
		}
	}
	cout << dist[convert(n, n)];
}