2206 벽 부수고 이동하기
벽 부수고 이동하기
기존의 BFS 방문 처리로는 해결 불가능한 문제
https://www.acmicpc.net/problem/2206
1. 문제
간단 설명
N*M 의 맵에서
1은 벽, 0은 길
(1,1) 에서 (N, M)까지 도달하는 최단경로 구하기
그런데 벽 하나를 부실 수 있다
2. 문제 분석
첫 시도한 알고리즘
1
2
3
4
1. 맵을 입력받으면서 벡터에 1로 지정된 벽을 등록
2. 벡터를 순회하면서 벽을 하나씩 부수고 BFS돌림
3. 최단 경로를 구하고 다시 벽을 원복
4. 이를 벽 벡터 끝까지 순회
하나씩 부수고 BFS 돌리고, 복구하는 과정을 반복하는 방법으로 풀이
그러나 벽을 부수고 원복하는 과정은 약 N * M번 반복해야하므로 약 O(N*M)
BFS도 약 O(N*M)
이므로 최악의 시간 복잡도는 약 10^12정도 나온다
1억이 약 1초라고 계산해도 1000초정도 나오는듯
시간 초과로 실패!
알고리즘
3차원 visited를 이용해야 한다고 한다
기존에 visited[y][x] 2차원 배열을 이용해서 풀이했다면
visited[y][x][2] 3차원 배열을 이용한다
기존의 건물이 1층짜리라고 생각하면, 3차원 배열은 2층짜리 건물이라고 생각하면 된다
예를 들어 visited[5][5][0]은 (5,5)까지 오는데 벽을 한번도 안 부신 경우의 거리를,
visited[5][5][1] (5,5)까지 오는데 벽을 한번이라도 뚫고 온 경우 걸린 거리를 기록한다
벽을 부순 경우 1층에서 2층으로 올려보내버려 거기서부터 계산한다
내려오는 경우는 없다 (벽을 부쉈으면 끝임!)
1
2
3
4
5
6
7
8
9
10
11
12
13
1. 입력받기
2. BFS 시작
2-1. (0, 0), 0층에서 시작. (0,0,0)을 큐에 넣고, visited에도 방문처리해줌
2-2. 큐가 빌때까지 다음을 반복
2-2-1. 현재 큐의 맨 앞을 꺼냄
2-2-2. (N-1, M-1) 도착 좌표인지 확인후 맞다면 visited[N-1][M-1][현재 층]을 리턴함
2-2-3. 아니라면 4방향 탐색 시작
2-2-4. 다음 확인할 좌표가 경계 밖이라면 패스
2-2-5. 다음 확인 좌표가 이미 방문한 곳이라면 패스
2-2-6. 다음 확인 좌표가 통과 가능한 곳이라면
2-2-6-1. 기존 BFS처럼 처리한다. 방문처리해주고, 큐에 넣는다
2-2-7. 통과 불가능한 곳이지만, 벽을 부술 수 있는 기회가 남아있다면(0층이라면)
2-2-7-1. 벽을 부수고, 큐에 이를 등록한다 (1층 올려보낸다)
예시
다음과 같은 벽이 있을때 최단 경로 구하기
N=5, M=5 왼쪽부터 (0,0)이고 파란색이 벽이다
통과 가능한곳을 따라 쭉 이동하다가 벽을 만나면
한층 올라가서 이어서 탐색을 계속한다
(실제로는 1에서 1층 올라갔다가, 2에서도 2층 올라갔다가 하지만 이해를 위해 간단히 표현함)
최단경로는 이렇게 된다
필요변수
가로 세로 N M,
2차원 맵 배열 map
3차원 방문체크 배열 visited[y][x][floor]
좌표 및 현재 층수 구조체 struct{int y, int x, int floor}
등등
주의점
문자열로 맵 정보가 주어짐. 문자 하나씩 받아 맵에 넣을 것
3차원 배열시 디버깅이 힘듬. 각 층마다 출력하는 방식을 이용했음
3. 소스코드
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
#include <iostream>
#include <queue>
using namespace std;
#define MAX 1001
int N, M;
int map[MAX][MAX];
int visited[MAX][MAX][2]; //3차원 배열 [y][x][벽 부순 여부]
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
struct Node {
int y;
int x;
int floor; // 벽을 부순 경우를 층수로 구분했음 0층은
};
// 디버그용 출력 함수
void debug_print(int y, int x, int floor) {
cout << "=======================================" << endl;
printf("Now : (%d, %d), Level : %d\n", y, x, floor);
for (int y = 0; y < N; y++) {
for (int x = 0; x < M; x++) {
cout << visited[y][x][floor] << " ";
}
cout << endl;
}
}
int BFS() {
queue<Node> qu;
visited[0][0][0] = 1; // (0,0)에서 벽을 부수지 않은 층에서 출발
qu.push({ 0,0,0 });
while (!qu.empty()) {
Node now = qu.front();
qu.pop();
// debug_print(now.y, now.x, now.floor);
if (now.y == N - 1 && now.x == M - 1) {
return visited[now.y][now.x][now.floor];
}
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue; // 경계처리
if (visited[dy][dx][now.floor] != 0) continue; // 이미 방문한곳이라면 패스
//
// 통과 가능한곳
if (map[dy][dx] == 0) {
// 기존 BFS와 똑같이 처리해준다
visited[dy][dx][now.floor] = visited[now.y][now.x][now.floor] + 1; // 현재 visited값에 +1해서 저장해준다
qu.push({ dy, dx, now.floor }); // 같은 층에서 계속 논다
}
// 벽이지만 한번 부술 수 있는 경우
else if (map[dy][dx] == 1 && now.floor == 0) {
// 윗층으로 올려보낸다
visited[dy][dx][now.floor + 1] = visited[now.y][now.x][now.floor] + 1;
qu.push({ dy, dx, now.floor + 1 });
}
}
}
return -1;
}
int main() {
// 1. 입력받기
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M;
for (int y = 0; y < N; y++) {
string tmp; cin >> tmp;
for (int x = 0; x < tmp.size(); x++) {
map[y][x] = tmp[x] - '0';
}
}
// 2. BFS
int ret = BFS();
if (ret == -1) {
cout << -1;
}
else {
cout << ret;
}
return 0;
}
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
// 시간초과난 알고리즘
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 1001
int N, M;
int map[MAX][MAX];
int visited[MAX][MAX];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
struct Node {
int y;
int x;
int level;
};
vector<Node> wall;
int BFS() {
memset(visited, 0, sizeof(visited));
queue<Node> qu;
qu.push({ 0,0,0 });
visited[0][0] = 1;
while (!qu.empty()) {
Node now = qu.front();
qu.pop();
if (now.y == N - 1 && now.x == M - 1) {
return now.level + 1;
}
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue;
if (map[dy][dx] == 1) continue;
if (visited[dy][dx] == 1) continue;
visited[dy][dx] = 1;
qu.push({ dy,dx,now.level + 1 });
}
}
return 21e8;
}
int main() {
freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M;
// 1. 맵을 입력받으면서 벽을 등록한다
for (int y = 0; y < N; y++) {
string tmp;
cin >> tmp;
for (int x = 0; x < tmp.size(); x++) {
map[y][x] = tmp[x] - '0';
if (map[y][x] == 1) {
wall.push_back({ y,x,0 });
}
}
}
// 벽을 하나 선택하여 부수고 이동해본다
int min_dis = 21e8;
for (Node e : wall) {
map[e.y][e.x] = 0;
min_dis = min(min_dis, BFS());
map[e.y][e.x] = 1;
}
if (min_dis == 21e8) {
cout << -1;
}
else {
cout << min_dis;
}
return 0;
}
참고 :
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.