백준 16197. 두 동전
알고리즘 중급 문제 중 531 - 브루트 포스 - 재귀(연습)
1. 간단 설명
N*M 크기의 보드판과 4개의 버튼으로 이루어진 게임
각 칸은 비어있거나, 벽임
두 개의 빈칸에 동전이 하나씩 놓여있고 두 동전의 위치는 다르다
버튼은 “왼쪽”, “오른쪽”, “위”, “아래”와 같이 4가지가 있음
버튼을 누르면 두 동전이 버튼에 쓰여있는 방향으로 동시에 이동함
동전이 이동하려는 칸이 벽이면, 동전은 이동하지 않는다
동전이 이동하려는 방향에 칸이 없으면, 동전은 보드 바깥으로 떨어진다.
그 외의 경우에는 이동하려는 방향으로 한 칸 이동한다.
이동하려는 칸에 동전이 있는 경우에도 한 칸 이동한다.
두 동전 중 하나만 보드에서 떨어트리기 위해 최소 버튼을 몇번 눌러야 하는지 구하는 프로그램
예시
- 예제 1
1 2
1 2 oo
한번 움직여서 떨어트릴 수 있음
- 예제 2
1 2 3 4 5 6 7
6 2 .. .. .. o# o# ##
위로 3번 굴리면 위쪽 동전이 먼저 떨어진다
- 예제 3
1 2 3 4 5 6
5 3 ### .o. ### .o. ###
동전을 하나만 떨어트리는 방법은 없으므로 -1을 출력한다
- 예제 4
1 2 3 4 5 6
5 3 ### .o. #.# .o. ###
3번만에 하나만 떨어트릴 수 있다
- 예제 5
1 2 3 4 5 6 7 8
7 6 ###### ##o..# ####.# #o##.# ####.# .....# ######
11번만에 동전 하나를 떨어트릴 수 있으나, 10번을 넘어가면 -1을 출력하라고 했기 때문에
-1을 출력한다
3. 알고리즘
BFS를 이용해 동전을 두개 동시에 움직이는 방법을 사용했다
특정 조건에서 하나의 동전이 떨어진 경우, 지금까지 몇번 움직였는지를 출력하는 것
그러나 여러 난관에 부딛쳤는데
동전 하나의 방문 처리는 2차원 visited 배열을 사용하면 가능하지만, 2개는 어떻게 처리할 것인가?
동전 2개를 이동할 경우 발생할 수 있는 케이스들은?
등이 있었다
1. 두개의 동전 방문 처리
먼저 2개의 동전 방문처리는 visited 배열을 4차원으로 사용함으로써 해결한다
visited[동전1의 Y][동전1의 X][동전2의 Y][동전2의 X]
4차원 visited 배열 BFS가 직관적이지 않아서 이해하는데 좀 어려웠다
물체 1개의 경우 2차원 visited 배열에서 (y, x)로 표현된다
보통 알고리즘을 풀 때 visted[y][x] = true 인 경우, 해당 위치를 방문했다고 표시함
그렇다면 물체가 2개인 경우 2D 공간에서 각각 이동한다고 가정해보자
각 물체의 위치를 독립적으로 추적해야한다
두 물체의 위치 조합은 (y1, x1) 과 (y2, x2)로 표현된다
이 위치 조합에 대해 방문 여부를 추적하기 위해 visited[y1][x1][y2][x2] = true로 표시하는것
예를 들어 (2,2), (3,3) 인 경우 visited[2][2][3][3] = 1로 설정한다.
이는 첫번째 물체가 (2,2), 두번째 물체가 (3,3)에 있는 상태를 이미 탐색했다는 뜻이다
더 나아가서 3차원 위치 좌표에서, 물체가 하나라면 visited[z][y][x],
물체가 두개라면 visited[z1][y1][x1][z2][y2][x2] 와 같이 표시할 수 있을 것이다
2. 두 동전을 이동할 때 발생할 수 있는 경우의 수들
동전을 두개를 이동할 때 발생할 수 있는 경우들은 다음과 같다
- 동전 두개가 벽에 막힌다
- 동전 두개가 맵 밖으로 떨어진다
- 동전 하나는 맵 안에, 하나는 맵 밖으로 떨어진다
- 동전 하나는 벽에 막히고, 하나는 이동한다
- 동전 두개가 이상 없이 해당 방향으로 한칸씩 이동한다
동전을 움직여서 3번 케이스일때, 현재까지 움직인 회수를 출력하면 된다
알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
1. N과 M을 입력받고, 맵 정보를 입력받는다
1-1. 맵 정보를 입력받으면서 동전의 좌표를 입력받는다
2. 동전 2개의 좌표를 큐에 넣고, BFS를 시작한다
2-1. 큐의 맨 앞에서 두 동전의 위치를 꺼낸다
2-2. 만약 지금까지 10번 이상 움직였다면 "-1" 출력 후 종료
2-3. 현재 동전들 위치에서 다음 이동할 좌표를 계산한다
2-3-1. 만약 두 동전이 모두 벽에 부딛쳤다면, 패스
2-3-2. 만약 두 동전이 맵 밖으로 떨어진 경우, 패스
2-3-3. 만약 두 동전 중, 하나만 맵 밖으로 떨어진 경우
- 해당 케이스가 찾던 케이스이므로 이동회수를 출력 후 종료한다
2-3-4. 두 동전 중 하나는 벽에 막히고, 하나는 이동 가능한 경우
- 길막당한 동전의 다음 이동 좌표를 현재 좌표로 수정한다(움직이지 못하므로)
2-3-5. 만약 두 동전의 해당 좌표를 방문한적이 없다면 큐에 이동회수 + 1 해서 넣는다
필요 변수
- 맵 세로, 가로 크기
int N, M(1 ≤ N, M ≤ 20) - 맵 정보를 저장할
char map[21][21]. 맵 정보는 문자로 주어짐 - 두 동전의 방문 기록 4차원 배열
visited[y1][x1][y2][x2] - 4방향 배열
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 } - BFS에 사용하기 위한 두 동전의 좌표와 이동회수 구조체
coins{동전1 좌표, 동전2 좌표, 이동 회수}
4. 소스코드
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <vector>
#include <queue>
#define MAX 21
using namespace std;
int N, M;
char map[MAX][MAX];
bool visited[MAX][MAX][MAX][MAX];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
vector<pair<int, int>> v;
struct coins {
int y1, x1; // 동전1의 좌표
int y2, x2; // 동전2의 좌표
int cnt; // 몇번 이동했는지를 기록
};
void Input() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M;
for (int y = 0; y < N; y++) {
string str; cin >> str;
for (int x = 0; x < str.size(); x++) {
map[y][x] = str[x];
if (map[y][x] == 'o') {
v.push_back({ y,x });
}
}
}
}
// 동전의 좌표를 받아 맵 밖으로 나갔는지 체크하는 함수
bool OutofMap(pair<int, int> coin) {
if (coin.first < 0 || coin.first >= N || coin.second < 0 || coin.second >= M)
return true;
return false;
}
void BFS() {
// 동전 두개의 위치를 저장하는 큐
queue<coins> qu;
qu.push({ v[0].first, v[0].second, v[1].first, v[1].second, 0});
visited[v[0].first][v[0].second][v[1].first][v[1].second] = true;
while (!qu.empty()) {
coins now = qu.front();
qu.pop();
// 만약 10번보다 넘어가면 더이상 보지 않음
if (now.cnt >= 10) {
cout << "-1";
return;
}
for (int t = 0; t < 4; t++) {
// 코인의 다음 좌표
pair<int, int> coin1, coin2;
coin1.first = now.y1 + direct[t][0];
coin1.second = now.x1 + direct[t][1];
coin2.first = now.y2 + direct[t][0];
coin2.second = now.x2 + direct[t][1];
// 1. 두 동전이 모두 벽에 부딪친 경우
if (map[coin1.first][coin1.second] == '#' && map[coin2.first][coin2.second] == '#') {
continue;
}
// 2. 두 동전이 모두 맵 밖으로 떨어진 경우
if (OutofMap(coin1) && OutofMap(coin2)) {
continue;
}
// 3. 두 동전 중 하나만 맵밖으로 떨어진 경우
if ((OutofMap(coin1) && !OutofMap(coin2)) || (!OutofMap(coin1) && OutofMap(coin2))) {
cout << now.cnt + 1;
return;
}
// 4. 하나의 동전만 벽을 만난 경우, 이동하지 못하므로 좌표를 원상복귀해줌
if (map[coin1.first][coin1.second] == '#') {
coin1.first = now.y1;
coin1.second = now.x1;
}
else if (map[coin2.first][coin2.second] == '#') {
coin2.first = now.y2;
coin2.second = now.x2;
}
// 5. 방문처리 후 큐에 넣기
if (visited[coin1.first][coin1.second][coin2.first][coin2.second] == false) {
visited[coin1.first][coin1.second][coin2.first][coin2.second] = true;
qu.push({ coin1.first, coin1.second, coin2.first, coin2.second, now.cnt+1 });
}
}
}
cout << "-1";
return;
}
int main() {
Input();
BFS();
return 0;
}
DFS를 이용한 풀이 추가
알고리즘
1
2
3
4
5
6
7
8
9
10
1. 현재 좌표에서 4방향으로 깊이 우선 탐색을 시도해본다
2. DFS
2-1. 10번 이상 움직였다면 더이상 들어가지 않는다
2-2. 다음 이동 좌표를 계산
2-3. 동전이 두개 다 밖으로 떨어졌다면 패스
2-4. 둘 중 하나만 떨어졌다면 정답이므로 이를 기록
2-5. 동전이 벽에 막힌다면, 좌표를 이전 좌표로 덮어쓰기
- 중복체크를 여기서 진행함
- 만약 두 동전 다 벽에 막혀서 좌표가 갱신되지 않았다면, 여기서 쳐낼 수 있음
2-6. 방문처리 후 {움직인 회수+1, 이동할 동전 좌표들}을 매개변수로 DFS 호출
DFS를 이용한 풀이
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
98
99
100
101
102
103
104
#include <iostream>
using namespace std;
int N, M;
char map[21][21];
bool visited[21][21][21][21]; // 두 동전의 위치를 기록하는 4차원 배열
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };
int min_res = 21e8;
struct coin {
int y;
int x;
} c1, c2;
void Input() {
// freopen_s(new FILE*, "input.txt", "r", stdin);
cin >> N >> M;
bool flag = false;
for (int i = 0; i < N; i++) {
string tmp; cin >> tmp;
for (int j = 0; j < M; j++) {
map[i][j] = tmp[j];
// 동전 위치 기록
if (map[i][j] == 'o') {
if (!flag) {
c1.y = i;
c1.x = j;
flag = true;
}
else {
c2.y = i;
c2.x = j;
}
}
}
}
}
// 코인이 맵 밖으로 떨어졌는지 체크하는 함수
bool CheckCoin(coin c) {
return (c.y >= 0 && c.y < N && c.x >= 0 && c.x < M);
}
void DFS(int level, coin c1, coin c2) {
if (level > 10) {
return;
}
// 4방향으로 이동 시도
for (int t = 0; t < 4; t++) {
// 동전의 다음 이동 방향
coin d1 = { c1.y + direct[t][0], c1.x + direct[t][1] };
coin d2 = { c2.y + direct[t][0], c2.x + direct[t][1] };
bool coin1_alive = CheckCoin(d1);
bool coin2_alive = CheckCoin(d2);
// 1. 두개 다 떨어진 경우
if (!coin1_alive && !coin2_alive) {
continue;
}
// 2. 둘 중 하나만 떨어진 경우 정답
else if ((coin1_alive && !coin2_alive) || (!coin1_alive && coin2_alive)) {
min_res = min(min_res, level + 1); // 다음 이동에서 정답이기 때문에 +1해줌
return;
}
// 3. 동전이 벽에 막힌 경우
if (map[d1.y][d1.x] == '#') {
d1 = c1;
}
if (map[d2.y][d2.x] == '#') {
d2 = c2;
}
if (visited[d1.y][d1.x][d2.y][d2.x]) continue;
visited[d1.y][d1.x][d2.y][d2.x] = true;
DFS(level + 1, d1, d2);
visited[d1.y][d1.x][d2.y][d2.x] = false;
}
}
int main() {
Input();
DFS(0, c1, c2);
if(min_res > 10){
cout << "-1";
}
else {
cout << min_res;
}
return 0;
}
DFS 또한 어디서 방문처리를 해야할지 햇갈려서 시간을 잡아먹었다
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.