https://www.acmicpc.net/problem/17090
17090번: 미로 탈출하기
크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한
www.acmicpc.net
각 칸은 방향이 정해져 있기 때문에 하나의 방향으로만 이동하여 경로는 정해져 있게 된다. 즉 탈출하는 경로를 찾으면 해당 경로에 해당하는 칸들은 모두 탈출 가능하다. 마찬가지로 탈출할 수 없는 경로가 있다면 해당 칸들은 모두 탈출 불가능하다. 참고로 경로를 따로 저장해놨다가 나중에 다시 한번에 체크해주는 방식으로 구현하면 시간 초과가 발생하므로 DFS로 구현해야 한다.
3 3
DDR
DLU
LLL
문제의 2번째 예제로 예를 들어보면 첫 번째 칸(0, 0)인 D에서 출발하면 정해진 방향에 따라 D-D-L의 경로로 탈출이 가능하다. 그러면 당연히 (1, 0)인 D에서도 D-L 로도 탈출 가능하고, (2, 0) L에서도 탈출 가능하다. 정확히는 L에서 탈출이 가능한 것이고 위의 D에서는 L로 향하게 방향이 되어있기 때문에 마찬가지로 탈출이 가능하다.
3 3
DDR
DLU
LLL
다음에 (0, 1) 칸인 위의 파란색 D에서 출발하면 아래로 내려와 L에 도착하고 L에서는 (1, 0)인 D에 도착한다. 그러면 위에서 이미 탈출 가능하다고 확인되었으므로 D에서 L까지 오는 경로는 모두 탈출 가능하다고 판단이 가능하다.
3 4
RRDD
RRDR
DULU
문제의 예제 입력 4번을 마지막 예시로 들어보면 처음 (0, 0)인 R에서 출발했을 때, R-R-D-D-L-U-R까지 왔다가 다시 D로 와서 사이클이 발생하기 때문에 탈출이 불가능하다. 이때의 각 경로에서는 탈출이 불가능하다는 것을 저장해놓으면 다음 (0,1), (0,2) 등의 빨간 경로에서는 다시 탐색할 필요가 없다.
3 4
RRDD
RRDR
DULU
마찬가지로 (1, 0)에서 출발하면 미리 저장해놓은 탈출할 수 없는 경로인 (1, 1) R에 도착하므로 탈출할 수 없는 칸이라는 것을 금방 알 수 있다.
이제 구현을 위해서는 문자를 입력받을 map배열 이외에 두 가지 배열을 더 사용하였다.
x, y 칸에서 탈출이 가능한지 저장할 check배열과 매번 각 탐색에서 방문했는지 확인할 visit배열을 사용하였다.
check배열의 값이 1이면 탈출 가능 / 2이면 탈출 불가능 / 0이면 아직 확인 안 됨으로 해놓고 구현했다.
또한, 이동한 경로를 저장하기 위해서 DFS를 사용하였다. 이동할 수 있는 칸까지 계속 이동하다가 탈출에 성공하거나 사이클이 발견돼서 실패하는 칸을 발견할 때까지 쭉쭉 탐색을 한다. 탈출에 성공했다면 true값을 리턴하고 실패했다면 false값을 리턴한다. DFS로 리턴 받은 값이 true이면 현재 칸에서 탈출이 가능하다는 뜻이므로 check배열 값을 1로 바꿔주고 탐색에서 돌아왔으므로 visit배열은 false로 바꿔준다. 반대로 false를 리턴 받았다면 check배열의 값을 2로 해주고 visit배열은 마찬가지로 false로 바꿔준다.
다시 정리를 해보면 복잡해 보이긴 하지만 아래와 같다.
- 입력을 받는다.
- 모든 칸을 검사하여 탈출할 수 있는지 검사한다.
- 이미 탈출 불가능한 칸으로 확인되었다면 DFS탐색을 하지 않고 다음 칸으로 넘어간다.
- 이미 탈출 가능한 칸으로 확인되었다면 정답 카운트를 증가시키고 DFS탐색을 하지 않는다. 마찬가지로 다음 칸으로 넘어간다.
- 확인되지 않은 칸이라면 DFS로 이동해서 경로를 확인하고 탈출할 수 있다면 정답 카운트를 증가시킨다.
- 탈출할 수 있는지 검사하기 위해 DFS를 진행한다.
- 해당 칸에 적혀 있는 문자에 따라 좌표를 이동한다.
- 범위를 벗어나면 탈출에 성공한 것이므로 해당 좌표의 check배열 값을 1로 바꿔주고 true를 리턴한다.
- 방문한 칸의 check배열을 값이 1이라면 이미 탈출 가능한 칸이라고 확인됐으므로 check배열의 값을 1로 바꾸고 true를 리턴한다.
- visit배열을 확인하여 이번 탐색에서 방문했던 칸을 다시 방문하거나(cycle 발생) check배열을 확인했을 때 값이 2로 이미 탈출 불가능한 칸이라고 확인됐으면 check배열의 값을 2로 해주고 false를 리턴한다.
- 위의 경우들이 아닌 이동한 칸에서 이동을 계속하는 경우에는 DFS탐색을 계속해주면 된다. visit배열을 true값으로 바꿔놓고 재귀 호출로 다음 칸으로 이동한고, 재귀 호출에서 돌아오면 visit배열을 다시 false값으로 바꿔준다. 탐색 결과에 따라 check배열의 값을 바꿔주면 되는데, 결과는 위의 3가지 상황 중에서 true나 false를 리턴 받은 값이다. 이전의 호출 함수에게도 이 결과를 그대로 리턴해줘서 현재 경로의 해당하는 모든 칸에 탈출이 가능한지 체크하도록 해준다.
DFS의 기본 개념을 알고 있다면 어렵지 않은 문제다.
|
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
|
#include <iostream>
using namespace std;
int n, m;
char map[501][501];
bool visit[501][501];
int check[501][501];
bool solve(int r, int c) {
//이동 전 위치 저장
int x = r;
int y = c;
char dir = map[r][c];
if (dir == 'U') r -= 1;
else if (dir == 'R') c += 1;
else if (dir == 'D') r += 1;
else c -= 1;
if (r < 0 || c < 0 || r >= n || c >= m) {
//탈출
check[x][y] = 1;
return true;
} else if (check[r][c] == 1) {
//탈출할 수 있는 경로
check[x][y] = 1;
return true;
} else if (visit[r][c] || check[r][c] == 2) {
//방문했던 곳으로 다시 돌아오거나(cycle) || 탈출할 수 없는 경로
check[x][y] = 2;
return false;
}
else {
visit[r][c] = true;
bool flag = solve(r, c);
visit[r][c] = false;
if (flag) check[r][c] = 1;
else check[r][c] = 2;
return flag;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> map[i];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (check[i][j] == 2) continue; //탈출불가능
if (check[i][j] == 1) ans++; //탈출가능
else {
if (solve(i, j)) ans++;
}
}
}
cout << ans << '\n';
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 16401. 과자 나눠주기 (2) | 2020.04.29 |
|---|---|
| [BOJ] 2174. 로봇 시뮬레이션 (0) | 2020.04.28 |
| [BOJ] 10711. 모래성 (0) | 2020.04.27 |
| [BOJ] 2866. 문자열 잘라내기 (0) | 2020.04.21 |
| [BOJ] 5427. 불 (0) | 2020.04.19 |