백준 2206번 : 벽 부수고 이동하기 / C++
2023. 3. 16. 14:26ㆍ개인공부/코딩테스트
처음에는 벽을 한개씩 부스는 연산을 했었는데 시간초과가 나거나 메모리 초과가 발생해서 접근방법을 벽을 부순 경우와 부수지 않은 경우로 케이스를 나누어서 해결하였다.
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
|
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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Pos
{
int irow;
int icol;
bool Breaking;
Pos(int _row, int _col, bool tf)
:irow(_row)
, icol(_col)
,Breaking(tf)
{}
};
int N, M; // row , col
bool arr[1000][1000]{};
bool visited[1000][1000]{}; // 벽을 부수지 않음
bool visited2[1000][1000]{}; // 벽을 부숨
bool NowClear = false;
int BFScount = 1;
queue<Pos> Q;
void BFS()
{
queue<Pos> tmp;
while (!Q.empty())
{
Pos now = Q.front();
if (now.irow == N - 1 && now.icol == M - 1) // 찾음
{
NowClear = true;
queue<Pos> clear;
Q = clear;
return;
}
if (now.Breaking == false) // 벽을 부순 경우
{
// up row-1
if (now.irow > 0 && visited[now.irow - 1][now.icol] == false && arr[now.irow - 1][now.icol] == 0)
{
visited[now.irow - 1][now.icol] = true;
tmp.push(Pos(now.irow - 1, now.icol, false));
}
// down row+1
if (now.irow + 1 < N && visited[now.irow + 1][now.icol] == false && arr[now.irow + 1][now.icol] == 0)
{
visited[now.irow + 1][now.icol] = true;
tmp.push(Pos(now.irow + 1, now.icol,false));
}
// left col-1
if (now.icol > 0 && visited[now.irow][now.icol - 1] == false && arr[now.irow][now.icol - 1] == 0)
{
visited[now.irow][now.icol - 1] = true;
tmp.push(Pos(now.irow, now.icol - 1,false));
}
// right col+1
if (now.icol + 1 < M && visited[now.irow][now.icol + 1] == false && arr[now.irow][now.icol + 1] == 0)
{
visited[now.irow][now.icol + 1] = true;
tmp.push(Pos(now.irow, now.icol + 1, false));
}
// 벽을 부수는 경우
if (now.irow > 0 && visited[now.irow - 1][now.icol] == false && arr[now.irow - 1][now.icol] == 1)
{
visited2[now.irow - 1][now.icol] = true;
tmp.push(Pos(now.irow - 1, now.icol, true));
}
// down row+1
if (now.irow + 1 < N && visited[now.irow + 1][now.icol] == false && arr[now.irow + 1][now.icol] == 1)
{
visited2[now.irow + 1][now.icol] = true;
tmp.push(Pos(now.irow + 1, now.icol, true));
}
// left col-1
if (now.icol > 0 && visited[now.irow][now.icol - 1] == false && arr[now.irow][now.icol - 1] ==1)
{
visited2[now.irow][now.icol - 1] = true;
tmp.push(Pos(now.irow, now.icol - 1, true));
}
// right col+1
if (now.icol + 1 < M && visited[now.irow][now.icol + 1] == false && arr[now.irow][now.icol + 1] == 1)
{
visited2[now.irow][now.icol + 1] = true;
tmp.push(Pos(now.irow, now.icol + 1, true));
}
}
else
{ // up row-1
if (now.irow > 0 && visited2[now.irow - 1][now.icol] == false && arr[now.irow - 1][now.icol] == 0)
{
visited2[now.irow - 1][now.icol] = true;
tmp.push(Pos(now.irow - 1, now.icol, true));
}
// down row+1
if (now.irow + 1 < N && visited2[now.irow + 1][now.icol] == false && arr[now.irow + 1][now.icol] == 0)
{
visited2[now.irow + 1][now.icol] = true;
tmp.push(Pos(now.irow + 1, now.icol, true));
}
// left col-1
if (now.icol > 0 && visited2[now.irow][now.icol - 1] == false && arr[now.irow][now.icol - 1] == 0)
{
visited2[now.irow][now.icol - 1] = true;
tmp.push(Pos(now.irow, now.icol - 1, true));
}
// right col+1
if (now.icol + 1 < M && visited2[now.irow][now.icol + 1] == false && arr[now.irow][now.icol + 1] == 0)
{
visited2[now.irow][now.icol + 1] = true;
tmp.push(Pos(now.irow, now.icol + 1, true));
}
}
Q.pop();
}
Q = tmp;
++BFScount;
}
int main(void)
{
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N >> M;
for (int row = 0; row < N; ++row)
{
string str;
cin >> str;
for (int col = 0; col < M; ++col)
{
if (str[col] == '0')
arr[row][col] = 0;
else
arr[row][col] = 1;
}
}
visited[0][0] = true;
Q.push(Pos(0, 0, false));
while (!Q.empty())
{
BFS();
}
if (NowClear == true)
cout << BFScount;
else
cout << -1;
}
|
cs |
'개인공부 > 코딩테스트' 카테고리의 다른 글
| 백준 1753번 : 최단 경로 / C++ (0) | 2023.03.18 |
|---|---|
| 백준 1707번: 이분 그래프 / C++ (0) | 2023.03.16 |
| 백준 7575번 : 토마토 / C++ (0) | 2023.03.15 |
| 백준 2178번 : 미로 탐색 / C++ (0) | 2023.03.15 |
| 백준 1260번 : DFS와 BFS / C++ (0) | 2023.03.14 |