출처 : 백준
문제 보러가기 : 벽 부수고 이동하기
전형적인 최단거리 찾는 문제이지만 벽을 1회 부술 수 있다는 조건이 존재한다.
따라서 벽을 부순 경우와 부수지 않은 경우를 고려해야 한다.
문제에서 1칸씩 이동할 수 있으므로 최단 거리를 찾는 알고리즘으로 BFS를 사용하는 것이 적절할 것 같아 이를 이용하여 구현하였다.
단, 방문여부를 표시할 때 위에서 언급하였던 이미 벽을 부수고 방문한 경우와 부수지 않고 방문한 경우를 따져야 한다.
소스코드
문제 보러가기 : 벽 부수고 이동하기
전형적인 최단거리 찾는 문제이지만 벽을 1회 부술 수 있다는 조건이 존재한다.
따라서 벽을 부순 경우와 부수지 않은 경우를 고려해야 한다.
문제에서 1칸씩 이동할 수 있으므로 최단 거리를 찾는 알고리즘으로 BFS를 사용하는 것이 적절할 것 같아 이를 이용하여 구현하였다.
단, 방문여부를 표시할 때 위에서 언급하였던 이미 벽을 부수고 방문한 경우와 부수지 않고 방문한 경우를 따져야 한다.
소스코드
|
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
|
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int n, m;
int map[1000][1000];
bool visit[1000][1000][2];
queue<pair<pair<int, int>, pair<int, int>>> q;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < m; j++)
{
map[i][j] = str[j] - '0';
}
}
q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
int min = -1;
visit[0][0][0] = true;
while (!q.empty())
{
int x = q.front().first.first;
int y = q.front().first.second;
int time = q.front().second.first;
int dist = q.front().second.second;
q.pop();
if (x == n - 1 && y == m - 1)
{
min = dist;
break;
}
for (int i = 0; i < 4; i++)
{
int next_x = x + dx[i];
int next_y = y + dy[i];
if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m)
{
if (map[next_x][next_y] == 1 && time == 0)
{
visit[next_x][next_y][time + 1] = true;
q.push(make_pair(make_pair(next_x, next_y), make_pair(time + 1, dist + 1)));
}
else if (map[next_x][next_y] == 0 && visit[next_x][next_y][time] == false)
{
visit[next_x][next_y][time] = true;
q.push(make_pair(make_pair(next_x, next_y), make_pair(time, dist + 1)));
}
}
}
}
cout << min << "\n";
return 0;
}
|
cs |
댓글