https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동
www.acmicpc.net
시작 칸에서 마지막 칸까지의 최단 거리를 구하는 문제이기 때문에 bfs로 풀 수 있다.
다른 분의 풀이를 보니 dfs로 엄청 효율적으로 푸셨는데 코드 참고해서 나도 다시 풀어봐야겠다...
먼저 이 문제에서 중요한 포인트는 벽을 한 개 부수고 이동할 수 있다는 점이다. 이 부분이 이 문제의 어려운 점이다
즉, (x, y)칸에 도착했을 때 그 칸에 그냥 왔는지와 벽을 부수고 왔는지 구분해 주어야한다.
그래서 3차원 배열로 구현했다. 벽을 부수지 않은 경우[x][y][0], 부 순경 우 [x][y][1] 에 이동 경로를 저장했다.
이동할 칸이 벽인 경우, 아직 벽을 부수지 않았고 해당 칸에 아직 방문하지 않았으면 벽을 부수고 이동할 수 있다.
길인 경우에는 그냥 방문하지 않았으면 바로 큐에 넣어준다.
개인적으로 은근히 헷갈렸던 부분은 이동 경로의 최솟값을 찾아주는 부분이었다.
우선 (n-1, m-1) 칸에 저장되어 있기는 하지만, 벽을 부수고 온 경우가 더 적은 지 벽을 부수지 않고 바로 온경우가 더 적은지
알 수 없으므로 비교해주어야 한다. 그리고 두 곳에 모두 값이 0이라면 -1을 출력해주어야 한다.
나는 먼저 바로 온 경우(d[n-1][m-1][0])을 최솟값(min)으로 해놓고 벽을 부수고 온 경우(d[n-1][m-1][1])가 0이 아닌 경우에 값을 다시 비교해주었다.
결과적으로 둘 다 0 값을 가지고 있으면 min값도 0이 되므로 도착하지 못한 경우가 되고 -1을 출력한다.
그렇지 않은 경우에는 최솟값을 가지고 있는 min을 출력해준다.
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#include <cstdio>
#include <queue>
using namespace std;
int map[1000][1000];
int d[1000][1000][2];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
int n, m;
scanf("%d %d", &n, &m);
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
scanf("%1d", &map[i][j]);
}
}
//시작 칸을 큐에 넣어준다.
queue<pair<pair<int, int>, int> > q;
q.push(make_pair(make_pair(0,0),0));
//시작칸도 포함이므로 1부터 시작
d[0][0][0] = 1;
while(!q.empty()) {
int z = q.front().second;
q.pop();
for(int i=0; i<4; i++) {
int nx = x+dx[i];
int ny = y+dy[i];
//범위 체크
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
//벽인 경우
//z == 0 이고 (벽을 부수지 않았고), 벽을 부순상태인 다음 칸에 아직 방문하지 않은 경우
if(map[nx][ny] == 1 && z == 0 && d[nx][ny][1] == 0) {
q.push(make_pair(make_pair(nx,ny),1));
d[nx][ny][1] = d[x][y][z] + 1;
} else if(map[nx][ny] == 0 && d[nx][ny][z] == 0) {
//길인 경우 이동할 칸에 방문하지 않았으면 방문
q.push(make_pair(make_pair(nx,ny),z));
d[nx][ny][z] = d[x][y][z] + 1;
}
}
}
//마지막칸의 최솟값을 찾아준다.
int min = d[n-1][m-1][0];
if(min != 0) {
if(d[n-1][m-1][1] != 0 && min > d[n-1][m-1][1]) {
min = d[n-1][m-1][1];
}
} else {
if(d[n-1][m-1][1] != 0) {
min = d[n-1][m-1][1];
}
}
//도착하지 못한 경우 -1을 출력
if(min == 0){
printf("%d", -1);
} else {
printf("%d",min);
}
return 0;
}
Colored by Color Scripter
|
|