https://www.acmicpc.net/problem/17090
17090번: 미로 탈출하기
크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문
www.acmicpc.net
시간을 최대한 쾌적하게 사용해야한다.
총 4번의 시도 끝에 성공..
처음 방법
그냥 일반적으로 탐색하다가 밖에 나오면 성공!으로 했지만, 실패
두번째는 q_history를 만들어 성공한 경우 탐색한 칸들은 MAP_CHECK배열에 true로 넣어 그 칸에 도착시 자동으로
탈출이 가능하다고 했다. 하지만 또 시간초가
세번재는 q_history를 통해서 탈출하지 못하는 경우도 MAP_CHECK_NOT배열에 true로 전달, 그 칸에 도착시 자동으로
탈출 못하는 하지만 실패
다음 방법은 방문 여부를 확인하는 check배열을 밖으로 빼어 매번 false로 초기화 하는 방식이 아닌, 성공하든 실패하든
check을 false로 만드는 방법 , 즉 이동경로를 확인하는 q_history가 있으므로, 그걸로 false로 초기화, 결과는 성공.
코드는 다음과 같다.
|
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
83
84
85
86
87
88
89
90
91
92
|
#include <iostream>
#include <queue>
using namespace std;
int N, M;
char MAP[501][501];
bool MAP_CHECK[501][501];
bool MAP_CHECK_NOT[501][501];
bool check[501][501] = { false };
// U R D L
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };
int count_res = 0;
void check_clean(int index, queue<pair<int,int>> &q_history) {
if (index == 0) {
while (!q_history.empty()) {
MAP_CHECK_NOT[q_history.front().first][q_history.front().second] = true;
check[q_history.front().first][q_history.front().second] = false;
q_history.pop();
}
}
else if (index == 1) {
while (!q_history.empty()) {
MAP_CHECK[q_history.front().first][q_history.front().second] = true;
check[q_history.front().first][q_history.front().second] = false;
q_history.pop();
}
}
}
int dir_check(char c) {
if (c == 'U')
return 0;
else if (c == 'R')
return 1;
else if (c == 'D')
return 2;
else if (c == 'L')
return 3;
}
void solve(int x,int y) {
check[x][y] = true;
queue<pair<int, int>> q;
queue<pair<int, int>> q_history;
q.push(make_pair(x, y));
//cout << x << y << endl;
while (!q.empty()) {
int prev_x = q.front().first;
int prev_y = q.front().second;
int dir = dir_check(MAP[prev_x][prev_y]);
q_history.push(make_pair(prev_x,prev_y));
if (MAP_CHECK[prev_x][prev_y] == true) {
check_clean(1, q_history);
count_res++;
return;
}
if (MAP_CHECK_NOT[prev_x][prev_y] == true) {
check_clean(0, q_history);
return;
}
q.pop();
int next_x = prev_x + dx[dir];
int next_y = prev_y + dy[dir];
if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= M) {
if (check[next_x][next_y] == false) {
check[next_x][next_y] = true;
q.push(make_pair(next_x, next_y));
}
else {
check_clean(0, q_history);
return;
}
}
else {
check_clean(1, q_history);
count_res++;
return;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> N >> M;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++)
cin >> MAP[i][j];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
solve(i, j);
}
}
cout << count_res << endl;
}
|
cs |
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 1092] 배 (C++) (0) | 2021.08.21 |
|---|---|
| [백준 19237] 어른 상어 (C++) (0) | 2021.08.21 |
| [백준 14890] 경사로 (C++) (0) | 2021.08.20 |
| [백준 19236] 청소년 상어 (C++) (0) | 2021.08.19 |
| [백준 20057] 마법사 상어와 토네이도 (C++) (0) | 2021.08.18 |