문제
스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.
보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.
각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.
보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.
문제접근법.
1. 1초, 2초, ... 10초일 때마다 구슬이 빠지는지 확인을 해줘야 하므로, BFS가 적절하다고 생각해서 큐 자료구조를 써야 한다.
2. BFS의 WHILE문에서 4방향으로 보드를 기울이는 것을 구현해줘야 한다.
3. 구슬이 같은 행 혹은 같은 열에 있거나, 둘다 구멍에 빠지는 경우에 대해서 처리를 해줘야 한다.
3번에 대해서 코드를 간결하게 짜야, 코드가 단순해질 수 있다. 코드를 길게 짠 후에, 짧게 바꾸는 것을 추천한다.
각 구슬은 대해서 OP[4][2]배열을 통해서 이동이 이루어지고, 이동 후에 도착한 지점의 값 비교를 통해서 구슬간의 위치 관계를 정의해줄 것이다.
'만약 이동 후에 같은 위치에 있다면(연산에 의해서), 이동 거리 변화가 짧은 구슬이 다른 구슬보다 앞에 위치해야 한다.'
#......RB# 이 경우를 보면, 보드를 왼쪽으로 기울이면 R과 B는 연산에 의해서 같은 지점에 있는 것으로 판단된다. 이 경우에, 이동 거리의 변화가 짧은 것은 R이므로, B는 OP[4][2]에 의한 연산을 하나 취소해야 한다.
또한 bool 함수 check1, check2를 통해서, 구슬이 벽에 빠지는 것을 확인할 수 있는 if문을 사용하도록 했다.
해설코드(C++).
|
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
|
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef struct element{
int r1;
int c1;
int r2;
int c2;
element(int _r1, int _c1, int _r2, int _c2) : r1(_r1), c1(_c1), r2(_r2), c2(_c2) {};
}element;
int N, M;
int map[11][11];
int check[11][11][11][11];
int hole_r, hole_c, b_r, b_c, r_r, r_c;
char c;
queue<pair<element, int>> q;
int answer = -1;
int temp1, temp2, time;
int op[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
int main(void)
{
freopen("input.txt", "r", stdin);
memset(check, 0, sizeof(check));
cin >> N >> M;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
cin >> c;
if (c == '#') {
map[i][j] = 1;
}
else if (c == '.') {
map[i][j] = 0;
}
else if (c == 'R') {
map[i][j] = 0;
r_r = i;
r_c = j;
}
else if (c == 'B') {
map[i][j] = 0;
b_r = i;
b_c = j;
}
else if (c == 'O') {
map[i][j] = 0;
hole_r = i;
hole_c = j;
}
}
}
//BFS
q.push(make_pair(element(r_r, r_c, b_r, b_c), 1));
while (!q.empty()) {
// MOVE
for (int i = 0; i < 4; i++) {
int q_r_r = q.front().first.r1;
int q_r_c = q.front().first.c1;
int q_b_r = q.front().first.r2;
int q_b_c = q.front().first.c2;
check[q_r_r][q_r_c][q_b_r][q_b_c] = 1;
time = q.front().second;
bool check1= false, check2 = false;
// RED MOVE
while (map[q_r_r + op[i][0]][q_r_c + op[i][1]] != 1) {
q_r_r += op[i][0];
q_r_c += op[i][1];
if (q_r_r == hole_r && q_r_c == hole_c) {
check1 = true;
break;
}
}
// BLUE MOVE
while (map[q_b_r + op[i][0]][q_b_c + op[i][1]] != 1) {
q_b_r += op[i][0];
q_b_c += op[i][1];
if (q_b_r == hole_r && q_b_c == hole_c) {
check2 = true;
break;
}
}
// RED IN HOLE
if (check1 && !check2) {
answer = time;
break;
}
// BLUE IN HOLE
else if (!check1 && check2) {
continue;
}
// RED && BLUE IN HOLE
else if (check1 && check2) {
int val1 = abs(q_r_r - hole_r) + abs(q_r_c - hole_c);
int val2 = abs(q_b_r - hole_r) + abs(q_b_c - hole_c);
if (val1 < val2) {
answer = time;
break;
}
else
continue;
}
// RED && BLUE IN NOT HOLE
else {
if (q_r_r == q_b_r && q_r_c == q_b_c) {
int val1 = abs(q_r_r - q.front().first.r1) + abs(q_r_c - q.front().first.c1);
int val2 = abs(q_b_r - q.front().first.r2) + abs(q_b_c - q.front().first.c2);
if (val1 < val2) {
q_b_r -= op[i][0];
q_b_c -= op[i][1];
}
else {
q_r_r -= op[i][0];
q_r_c -= op[i][1];
}
}
if(!check[q_r_r][q_r_c][q_b_r][q_b_c])
q.push(make_pair(element(q_r_r, q_r_c, q_b_r, q_b_c), time + 1));
}
}
if (time > 10)
break;
if (answer != -1)
break;
q.pop();
}
cout << answer << endl;
return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘 > 백준' 카테고리의 다른 글
| [15684번] 사다리 조작 (0) | 2019.10.12 |
|---|---|
| [12100번] 2048 (Easy) (삼성코딩테스트) (0) | 2019.10.09 |
| [16236번] 아기상어(삼성 코딩 테스트) (0) | 2019.10.07 |
| [11052번] 카드 구매하기(C++, 다이나믹 프로그래밍) (0) | 2019.10.07 |
| [15685번] 드래곤 커브(삼성 코딩 테스트) (0) | 2019.10.07 |
