문제 출처 : https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동
www.acmicpc.net
이 문제는 벽을 부수거나 안 부수고 경로를 갈 수 있는데 벽을 부술 수 있는 기회는 딱 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
77
78
79
80
81
|
#include<stdio.h>
#include<queue>
#pragma warning(disable:4996)
using namespace std;
struct list
{
int x = 0;
int y = 0;
int cnt = 0;
int crash = 0;
};
queue <list> que;
int visit[1001][1001];
char arr[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int N, M;
int value = 1e9;
void BFS()
{
list temp;
{
list now = que.front();
que.pop();
int x = now.x;
int y = now.y;
if (x == N - 1 && y == M - 1)
{
value = cnt;
return;
}
for (int i = 0; i < 4; i++)
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < N && ny >= 0 && ny < M)
{
if (visit[nx][ny] == 0 && arr[nx][ny] == '0' &&crash==1)
{
visit[nx][ny]=2;
temp.x = nx;
temp.y = ny;
temp.crash = crash;
}
if (visit[nx][ny] != 1 && arr[nx][ny] == '0' && crash == 0)
{
visit[nx][ny] = 1;
temp.x = nx;
temp.y = ny;
temp.crash = crash;
}
if (visit[nx][ny] == 0 && arr[nx][ny] == '1' && crash == 0)
{
visit[nx][ny] = 2;
temp.x = nx;
temp.y = ny;
}
}
}
}
}
int main()
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++)scanf("%s", arr[i]);
visit[0][0] = 1;
BFS();
if (value == 1e9)printf("-1");
else printf("%d", value+1);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준 6593번 문제 ( 상범 빌딩 ) (0) | 2020.02.18 |
|---|---|
| 백준 5427번 문제 ( 불 ) (0) | 2020.02.18 |
| 백준 14247번 문제 ( 나무 자르기 ) (0) | 2020.02.14 |
| 백준 5014번 문제 ( 스타트링크 ) (0) | 2020.02.14 |
| 백준 3078번 문제 ( 좋은 친구 ) (0) | 2020.02.11 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~