백준 6087. 레이저 통신
너비 우선 탐색 문제인데, 한 방향으로 쭉 가는 문제
DFS로도 가능할 듯?
1. 간단 설명
W * H 크기의 지도가 주어진다
C 로 표시되어있는 두 칸을 레이저로 통신하기 위해 설치해야 하는 거울 개수의 최소값을 구하는 문제
레이저는 C에서만 발사할 수 있다
빈칸에 거울 ‘/’, ‘'을 설치해서 방향을 90도 회전시킬 수 있다
2. 예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
7 . . . . . . . 7 . . . . . . .
6 . . . . . . C 6 . . . . . /-C
5 . . . . . . * 5 . . . . . | *
4 * * * * * . * 4 * * * * * | *
3 . . . . * . . 3 . . . . * | .
2 . . . . * . . 2 . . . . * | .
1 . C . . * . . 1 . C . . * | .
0 . . . . . . . 0 . \-------/ .
0 1 2 3 4 5 6 0 1 2 3 4 5 6
7 1 1 1 1 1 1 0
6 0 0 0 0 0 0 C1
5 1 1 1 1 1 1 *
4 * * * * * 1 *
3 3 3 3 3 * 1 2
2 3 3 3 3 * 1 2
1 3 C 3 3 * 1 2
0 2 2 2 2 2 1 2
0 1 2 3 4 5 6
각 좌표의 숫자는 C1에서 시작해서
해당 좌표에 몇개의 거울을 놓았을 때 도달할 수 있는지를 기록한 것
3. 알고리즘
일반적인 2차원 방문 BFS로 풀어본다면
4방향 중 한쪽 방향으로 벽이나 맵 경계에 도달할 때 까지 쭉 가면서 방문처리하고,
방문했던 노드들을 쭉 큐에 넣는 방법을 생각했다
그리고 실제로 잘 동작하길래 제출했더니 메모리 초과 발생
(파이썬에서는 이 방법으로도 성공하는듯 함)
메모리 초과가 큐에서 발생하는 것으로 보아, 방문한 모든 노드들을 큐에 넣으면 안되는 것 같음
이를 방지하기 위해 visited[y][x][dir]를 사용하여 방향 벡터까지 저장하는 방문처리 배열을 사용함
즉 y, x에 어느 방향에서 왔는지를 처리해서 중복 계산을 줄일 수 있다
visited[y][x] 2차원 배열에서는 (y,x)위치에서 방문 여부만 체크하고, 방향에 따른 경로를 고려하지 않는다
동일한 위치를 다른 방향으로 방문해야하는 상태를 관리할 수 없어 중복 탐색이 발생한다
같은 (1,1)에 도달했더라도, 이게 위에서 온건지, 아래에서 온건지 구분이 불가능함
특정 위치에 여러번 방문하면서 큐에 중복 노드가 쌓이고, 이로 인해 큐의 메모리가 폭팔하는 문제가 발생
visited[y][x][dir]에서는 각 위치에서 방향별로 별도의 방문상태를 기록한다
배열의 크기가 더 크지만, 탐색 중에 중복 상태를 제거해서 메모리를 더 적게 사용한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1. W, H입력 받고 맵 정보 입력받기
1-1. 현재 칸이 C라면 기록해두기
1-2. 방문배열을 INF로 초기화
2. BFS 시작
2-1. C의 출발점을 방문처리 후, 큐에 넣는다
- visited[y][x][4]를 0으로 초기화하고, 큐에 넣는다
2-2. BFS 수행
- 큐에서 맨 앞 노드 꺼내기
- 4방향 탐색
- dy, dx 구하기
- 현재 방향과 t가 일치하지 않으면 거울 1 증가
- 맵 경계 체크
- 벽 체크
- 이미 방문한 기록이 현재 거울 수 보다 적다면 더이상 보지 않음
- 방문 체크 기록 및 큐에 넣기
4. 소스코드
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
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 101
using namespace std;
int W, H;
char map[MAX][MAX];
vector<pair<int, int>> c;
int visited[MAX][MAX][4]; // [y][x][dir] 방향별 최소 거울 설치 회수
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
struct Node {
int y;
int x;
int dir;
int mirrors;
};
void Input() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> W >> H;
for (int y = 0; y < H; y++) {
string tmp; cin >> tmp;
for (int x = 0; x < W; x++) {
map[y][x] = tmp[x];
if (map[y][x] == 'C') {
c.push_back({ y,x });
}
}
}
// memset
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
for (int d = 0; d < 4; d++) {
visited[y][x][d] = 21e8;
}
}
}
}
void BFS() {
// 시작 지점 초기화
queue<Node> qu;
for (int d = 0; d < 4; d++) {
int sy = c[0].first;
int sx = c[0].second;
visited[sy][sx][d] = 0;
qu.push({ sy,sx, d, 0 });
}
while (!qu.empty()) {
Node now = qu.front();
qu.pop();
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
int mirrors = now.mirrors + (now.dir != t); //방향이 다르면 거울 1 추가
if (dy < 0 || dx < 0 || dy >= H || dx >= W) continue; // 경계 처리
if (map[dy][dx] == '*') continue; // 벽 처리
if (visited[dy][dx][t] <= mirrors) continue; // 더 적은 거울로 이미 방문한 기록이 있다면 패스
visited[dy][dx][t] = mirrors;
qu.push({ dy, dx, t, mirrors });
}
}
}
int main() {
Input();
BFS();
int result = 21e8;
for (int t = 0; t < 4; t++) {
result = min(result, visited[c[1].first][c[1].second][t]);
}
cout << result;
return 0;
}
차원 방문 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
void BFS() {
// memset INF
for (int y = 0; y < H; y++) {
for (int x = 0; x < W; x++) {
visited[y][x] = 21e8;
}
}
queue<Node> qu;
visited[c[0].first][c[0].second] = 0;
qu.push({ c[0].first, c[0].second });
while (!qu.empty()) {
Node now = qu.front();
qu.pop();
for (int t = 0; t < 4; t++) {
int dy = direct[t][0] + now.y;
int dx = direct[t][1] + now.x;
// 한 방향으로 쭉 가본다
while (1) {
if (dy < 0 || dx < 0 || dy >= H || dx >= W) break; // 경계처리
if (map[dy][dx] == '*') break; // 벽
if (visited[dy][dx] < visited[now.y][now.x] + 1) break; // 지난적 있지만, 거울이 더 필요함
qu.push({ dy, dx });
visited[dy][dx] = visited[now.y][now.x] + 1;
dy += direct[t][0];
dx += direct[t][1];
}
}
}
}
3차원 방문처리 배열을 이용하는게, 2차원 방문처리를 이용하는 것 보다
메모리 효율이 더 좋다는게 잘 와닿지 않아 이해하는데 좀 어려웠다
고정된 크기는 2차원 배열이 더 작지만,
큐가 돌아가면서 2차원 + 방향 방문처리가 더 효율적으로 동작하여
메모리를 더 적게 사용할 수 있다는 것이 문제의 포인트였음
나중에 한번 더 풀어봐야겠다