문제
풀이
BFS를 이용하여 풀이하는 문제이다. Reference를 참조하였다. 매 단계마다 4가지를 고려한다. 벽을 부쉈는지, 갈 장소가 0으로 되어 있는지, 1로 되어 있는지. queue 에는 (x,y) 좌표와 (벽을 부순 횟수, 경로의 cnt) 가 담겨있고, visit함수에는 x,y 좌표와 벽을 부순 횟수를 index로 삼는다. 그래서 결과적으로, 벽이 있고, 벽을 부순 횟수가 0이라면, 그 좌표 + 벽을 부쉈다를 의미하는 visit함수를 true로 바꾸고 queue해준다. 혹은 벽이 없고 방문한 적이 없다면 그 곳을 방문한것으로 check하고 큐에 넣는다. 이렇게 가장 먼저 목표 지점에 도달한 것을 return 한다.
소스 코드
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
#include<iostream>
#include<string>
#include<queue>
#define endl "\n"
#define MAX 1000
using namespace std;
int N, M;
int MAP[MAX][MAX];
bool Visit[MAX][MAX][2];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
void Input()
{
cin >> N >> M;
for (int i = 0; i < N; i++)
{
string Inp;
cin >> Inp;
for (int j = 0; j < M; j++)
{
int Tmp = Inp[j] - '0';
MAP[i][j] = Tmp;
}
}
}
int BFS()
{
queue<pair<pair<int, int>, pair<int,int>>> Q;
Q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
Visit[0][0][0] = true;
while (Q.empty() == 0)
{
int x = Q.front().first.first;
int y = Q.front().first.second;
int B = Q.front().second.first;
int Cnt = Q.front().second.second;
Q.pop();
if (x == N - 1 && y == M - 1)
{
return Cnt;
}
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)
{
if (MAP[nx][ny] == 1 && B == 0)
{
Visit[nx][ny][B+1] = true;
Q.push(make_pair(make_pair(nx, ny), make_pair(B + 1, Cnt + 1)));
}
else if (MAP[nx][ny] == 0 && Visit[nx][ny][B] == false)
{
Visit[nx][ny][B] = true;
Q.push(make_pair(make_pair(nx, ny), make_pair(B, Cnt + 1)));
}
}
}
}
return -1;
}
void Solution()
{
int R = BFS();
cout << R << endl;
}
void Solve()
{
Input();
Solution();
}
int main(void)
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//freopen("Input.txt", "r", stdin);
Solve();
return 0;
}
