https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
처음 보면 탐색 방법으로 풀어야겠다는 생각이 딱 든다.
bfs를 이용해서 풀어보자!
일단 이 문제의 핵심은 벽을 1번 부술 수 있다. 그래서 나는 bool destory 변수를 두어 벽을 부수고 온 탐색인지 아닌지를 구분해 주었다. tuple을 사용하여 x좌표, y좌표, count, destory 이렇게 4개의 변수를 저장하여 큐에 넣어주는 식으로 구현하였다.
또 실수하지 말아야 할 것은 방문을 표기 하는 변수 visit[][]에 벽을 부수고 방문한 탐색과 벽을 부수지 않고 방문한 탐색을 나눠서 기록하지 않으면 어떤 현상이 발생하냐면
| 출 | (a) | (b) | (c) | (d) |
| x (1) | x | x | x | (e) |
| (2) | (f) | |||
| (3) | (g) | |||
| (4) | (k) | (j) | (i) | (h) |
| (5) | x | x | x | x |
| x | x | x | x | x |
| 도 |
x가 벽이다. 이렇게 되면 숫자로 시작한 탐색은 이미 벽을 뚫고 왔기 때문에 5번 이후 갈 곳이 없다. 그런데 문제는 영어로 시작한 탐색은 멀리서 돌아오기때문에 숫자 탐색보다 4위치에 늦게 도달하는데 visit을 구분해주지 않게 되면 이미 탐색한 위치로 되어 영어로 시작한 탐색은 종료한다. 영어로 시작한 탐색은 5번 위치로 가면 벽을 한번 부술 수 있기 때문에 도착에 도달 할 수 있음에도 없는 상황이 발생하기 때문에 꼭 visit 체킹을 할 때 벽을 부수고 온 탐색인지 아닌지를 구별해주는 것이 핵심이다. 나는 visit[2][1001][1001] 배열을 사용하여 visit[0][][]에는 벽을 부수지 않은 방문 visit[1][][]은 벽을 부수고 온 탐색의 방문을 기록해 주었다.
전체코드
|
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
#include<iostream>
#include <string>
#include <queue>
#include <tuple>
using namespace std;
int n, m;
int map[1001][1001] = {0};
bool visit[2][1001][1001]; //벽을 부수고 온지 아닌지 구별해서 저장
int dx[] = {0, 0, -1, 1}; //상하좌우
int dy[] = {1, -1, 0, 0}; //상하좌우
int ans = 1000 * 1000;
void bfs(int a, int b, int cnt, bool destory){
queue<tuple<int, int, int, bool>> q;
q.push(make_tuple(a, b, cnt, destory));
while(!q.empty()){
int x = get<0>(q.front());
int y = get<1>(q.front());
cnt = get<2>(q.front());
destory = get<3>(q.front());
q.pop();
if(x == m-1 && y == n-1){
ans = cnt;
break;
}
for (int i = 0; i < 4;i++){
int n_x = x + dx[i];
int n_y = y + dy[i];
if (n_x < m && n_x >= 0 && n_y < n && n_y >= 0){
if(destory){// 벽을 부수고 온지 아닌지 구별
if(!visit[1][n_y][n_x]){
if(map[n_y][n_x] == 0){
visit[1][n_y][n_x] = true;
q.push(make_tuple(n_x, n_y, cnt+1, destory));
}
}
}else{
if(!visit[0][n_y][n_x]){
if(map[n_y][n_x] == 0){
visit[0][n_y][n_x] = true;
q.push(make_tuple(n_x, n_y, cnt+1, destory));
}
else if(map[n_y][n_x] == -1){
destory = true;
visit[0][n_y][n_x] = true;
q.push(make_tuple(n_x, n_y, cnt+1, destory));
destory = false;
}
}
}
}
}
}
}
int main(){
cin >> n >> m;
string temp;
for (int i = 0; i < n;i++){
cin >> temp;
for (int k = 0; k < m; k++){
if(temp[k] == '1'){
map[i][k] = -1;
}
}
}
visit[0][0][0] = true;
bfs(0, 0, 1, false);
if(ans == 1000*1000){
cout << -1;
}
else{
cout << ans;
}
return 0;
}
/*void dfs(int x,int y,int cnt, bool destory){
cnt++;
if(x == m-1 && y == n-1){
if(ans > cnt){
ans = cnt;
}
}
for (int i = 0; i < 4;i++){
int n_x = x + dx[i];
int n_y = y + dy[i];
if (n_x < m && n_x >= 0 && n_y < n && n_y >= 0){
if(!visit[n_y][n_x]){
if(map[n_y][n_x] == 0 || map[n_y][n_x] > cnt+1){
map[n_y][n_x] = cnt+1;
visit[n_y][n_x] = true;
dfs(n_x, n_y, cnt, destory);
visit[n_y][n_x] = false;
}
else if(map[n_y][n_x] == -1 && !destory){
destory = true;
visit[n_y][n_x] = true;
dfs(n_x, n_y, cnt, destory);
visit[n_y][n_x] = false;
destory = false;
}
}
}
}
}시간초과*/
|
cs |
사용 문법 : bfs, tuple, queue
yea !
ps. 주석에 있는 코드는 dfs 코드인데 dfs 연습겸 풀어봤지만 시간초과로 막혔다. 많은 시도를 했지만 시간초과를 해결할 수 없었다. 나중에 다시 한번 dfs로 풀 수 있는 방법을 생각해 봐야겠다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 6593 상범빌딩 c++ [컴공과고씨] (0) | 2022.03.21 |
|---|---|
| 백준 2583 영역 구하기 c++ [컴공과고씨] (0) | 2022.03.19 |
| 백준 1260 DFS와 BFS C++ [컴공과고씨] (0) | 2022.03.19 |
| 백준 1003 피보나치 함수 C++ [컴공과고씨의 개발일지] (0) | 2022.03.19 |
| 백준 1074 Z c++ [컴공과고씨] (0) | 2022.03.18 |