https://www.acmicpc.net/problem/13459
13459번: 구슬 탈출
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
이 문제 같은 경우 제약 조건이 많아 차근차근 조건을 생각해 나가야 풀 수 있는 문제 였습니다.
문제 정리
바둑판 있음.
바둑판 가장자리는 벽으로 막혀있고 중간 중간에 벽이 있을 수 있음.
바둑판에 빨강, 파랑 1개씩 구슬 주어지고 구슬이 빠지는 구멍이 주어짐.
바둑판을 상하좌우로 기울일 수 있음.
바둑판을 기울이면 그 방향 끝까지 감. (구슬은 곂쳐질 수 없음.)
-> #......RB 였을때 왼쪽으로 기울이면 #RB..... 이 됨.
빨강 구슬을 구멍에 넣어야함.
이때 기울이는 횟수는 10번 이하로 해야하면 파란색 구슬은 구멍에 빠지면 안됨.
또한 빨강, 파란 구슬이 동시에 빠져서도 안됨.
기울이면 구슬은 동시에 움직이기 시작.
문제 해결 방식
이런 문제는 제약 조건을 잘 정리를 해서 하나씩 구현해 나아가면 됩니다.
파란 구슬 먼저 그 다음 빨간 구슬을 이동시키는 방식으로 구현했습니다.
(동시에 움직인다는 조건은 조건문을 통해 해결 할 수 있음.)
바둑판을 기울일 때 일어나는 상황
1. 벽을 만났다.
2. 구멍을 만났다.
3. 구슬을 만났다.
1번을 구현하기 위해 파란 구슬 부터 반복문을 사용하여서 기울인 방향으로 좌표를 벽을 만나기 전까지 하나씩 옮겨줍니다. 벽을 만나면 그 위치가 파란 구슬 위치가 됩니다.
그런데 가는 도중 2번 조건 구멍을 만났다면 파란 구슬이 빠졌기 때문에 이미 이것은 더 이상 볼 필요가 없습니다.
bool 변수로 불가능 표시를 해줍니다.
이제는 빨간 구슬을 이동 시킵니다.
이동 도중 2번 조건 구멍을 만났다면 빨간 구슬이 빠졌기 때문에 이 경우는 성공일 수도 있고 실패 일 수도 있습니다.
실패의 경우는 위의 파란 구슬이 들어간 경우입니다.
일단 빨간 구슬이 통과했으므로 bool 변수에 표시를 해 둡니다.
그 후 아까 말했던 동시에 빠진 경우를 체크하여서 동시에 빠진 경우 불가능으로 해주고 빨간 구슬만 빠진 경우는 정답으로 체크해 줍니다.
만약 그것이 아니라 구슬들이 만난 경우.
이 경우는 우리는 빨간 구슬과 파란 구슬을 독립적으로 벽까지 이동시켰기 때문에
위의 좌표 이동을 했을 때 빨간 색 구슬과 파란색 구슬의 위치가 같은 경우 생겨납니다.
이 경우 어느 구슬이 기울이는 방향 쪽에 있었는지가 중요합니다.
예를 들어서 우측으로 기울일 때 구슬들의 위치가 같다면 두 가지 경우가 생깁니다.
1. R..B...#
2. .B..R...#
위 두 경우를 고려해서 B가 앞 쪽일 때는 결과가 ...RB#
2번의 경우는 ..BR# 이렇게 됩니다.
그래서 방향으로 기울일 때 어느 구슬이 앞쪽에 있는지 확인 후 뒤쪽에 있던 구슬의 좌표를 빼줍니다.
여기서 중요한 건 우측과 좌측으로 기울이는 것은 X좌표에만 영향 받고
상하로 기울이는 것은 Y좌표에만 영향을 받기 때문에 조건식을 줄일 수 있습니다.
그래서 R의 X좌표가 B의 X좌표보다 큰 경우 오른쪽으로 기울일 때, 왼쪽으로 기울일 때 이렇게 두 조건을 고려해 주면됩니다.
마찬가지로 BX > RX 경우 오른쪽으로 기울일 때, 왼쪽으로 기울일 때 고려
다음 BY > RY는 위로 기울이는 경우, 아래로 기울이는 경우
마지막으로 RY > RX도 위 아래 고려
이렇게 해서 각 좌표를 구해주면 다음 빨간 구슬과 파란 구슬의 좌표를 구할 수 있습니다.
그 다음 이 좌표를 바로 큐에 넣는 것이 아니라 중복한 것을 빼주어야 합니다.
1. 전에 기울였던 방향으로 돌아가는 경우
2. 빨간 파란 구슬위치가 둘 다 기울이기 전과 똑같은 경우
1번 경우는 생각해보면 오른쪽으로 기울였다가 다시 왼쪽으로 기울이면 결국 똑같은 것을 반복하는 것이기 때문에 걸러주어야 하고
2번 경우도 마찬가지 입니다.
그래서 정답인지 아니면 불가능한 좌표인지 기울이는 횟수가 10이하인지 확인 후
큐에 구슬 좌표와 기울인 횟수, 기울인 방향(중복 확인 용) 이렇게 넣어주면 됩니다.
큐에 넣는 변수가 6개 이다 보니 tuple을 사용했습니다.
튜플은 간단히 pair와 비슷한데 pair 2개의 변수를 저장했다면 tuple은 다수의 변수를 저장할 수 있습니다.
조건들이 조금 복잡해서 이해가 안가신다면 코드 주석을 보면서 이해하셔도 좋습니다.
물론 제 코드가 엄청 깔끔하게 짜인 것은 아니지만 문제를 이해하는데는 충분할 것 같습니다.
전체코드
|
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
143
144
145
146
147
148
149
150
151
152
|
#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
using namespace std;
char map[11][11];
int n, m;
int bx, by, rx, ry; // 구슬 위치
int hx, hy; // 구멍 위치
int dx[] = {0, 0, 1, -1}; //하상우좌
int dy[] = {1, -1, 0, 0};
bool stop = false; // 빨간 구슬이 구멍에 들어갔는지
int result = 0;
bool checkHall(int a, int b){ // 구슬이 구멍에 빠졌는지 확인
if(a != hx || b != hy)
return false;
return true;
}
void bfs(){
queue<tuple<int, int, int ,int, int, int>> q;
q.push(make_tuple(bx, by, rx, ry, 1, -1));
while(!q.empty()){
if(stop){
result = 1;
return;
}
int bbx = get<0>(q.front()); // 현재 파란 구슬 좌표 변수
int bby = get<1>(q.front());
int rrx = get<2>(q.front()); // 현재 빨간 구슬 좌표 변수
int rry = get<3>(q.front());
int cnt = get<4>(q.front()); // 기울인 횟수
int bef = get<5>(q.front()); // 전에 어느 방향으로 기울였는지
q.pop();
for (int i = 0; i < 4; i++){
// 전에 왔던 방향으로 다시 가는 것은 중복 -> 갈 필요없음
if(bef == 0 && i ==1)
continue;
if(bef == 1 && i ==0)
continue;
if(bef == 2 && i ==3)
continue;
if(bef == 3 && i ==2)
continue;
if(stop){ // 빨간 구슬 들어간 경우
result = 1;
return;
}
int nbx = bbx; // 다음 파란 구슬 좌표 변수
int nby = bby;
int nrx = rrx; // 다음 빨간 구슬 좌표 변수
int nry = rry;
bool possible = true; // 다음 좌표로 갈 수 있는 경우인지
while(map[nby][nbx] != '#'){ // 벽을 만나면 종료
nbx += dx[i]; // 한 칸씩 좌표 이동
nby += dy[i];
if(checkHall(nbx, nby)){ // 구멍을 만났다.
possible = false; // 파란 구슬 들어감.
break;
}
}
while(map[nry][nrx] != '#'){
nrx += dx[i]; // 한 칸씩 좌표 이동
nry += dy[i];
if(checkHall(nrx, nry)){ // 구멍을 만났다.
stop = true;
break;
}
}
if(!possible && stop){ // 빨강 파란 구슬 동시에 빠진 경우
stop = false; // 불가능으로 바꾸어줌.
}else if(stop){
result = 1;
}
// 벽을 만날 때 까지 좌표를 + 해서 그 전 좌표로 이동 시켜줌
nbx -= dx[i];
nby -= dy[i];
nrx -= dx[i];
nry -= dy[i];
//두 개의 구슬이 만난 경우
if(nbx == nrx && nby == nry){
if(bbx > rrx){ // B좌표가 더 큰 경우
if(i == 2){ // 우측 기울 일 때.
nrx -= dx[i];
}else if (i == 3){ // 좌측 기울 일 때.
nbx -= dx[i];
}
}else if(bbx < rrx){
if(i == 2){
nbx -= dx[i];
}else if (i == 3){
nrx -= dx[i];
}
}else if(bby > rry){
if(i == 0){
nry -= dy[i];
}else if (i == 1){
nby -= dy[i];
}
}else if(bby < rry){
if(i == 0){
nby -= dy[i];
}else if (i == 1){
nry -= dy[i];
}
}
}
if(nbx == bbx && nby == bby && rrx == nrx && rry ==nry){
//두 구슬 위치가 기울이기 전과 같은 경우
possible = false;
}
if(!stop && possible && cnt + 1 <= 10){
q.push(make_tuple(nbx, nby, nrx, nry, cnt + 1,i));
}
}
}
}
int main(){
cin >> n >> m;
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cin >> map[i][j];
if(map[i][j] == 'B'){ // 초기 파란 구슬 위치
bx = j;
by = i;
}else if(map[i][j] == 'R'){ // 초기 빨간 구슬 위치
rx = j;
ry = i;
}else if(map[i][j] == 'O'){ // 구멍 위치
hx = j;
hy = i;
}
}
}
bfs();
if(stop) // 성공했다면
cout << result;
else
cout << 0;
return 0;
}
|
cs |
| 체감 난이도 | 걸린 시간 | 후기 | 사용 알고리즘 |
| 중상 | 1.5h | 조건들을 놓치지 않고 하나씩 생각하는데 시간이 조금 걸림 | BFS |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 5430 AC c++ [컴공과고씨] (0) | 2022.08.14 |
|---|---|
| 백준 14500 테트로미노 C++ [컴공과고씨] (0) | 2022.08.14 |
| 백준 2665 미로만들기 c++ [컴공과고씨] (2) | 2022.08.12 |
| 백준 20055 컨베이어 벨트 위의 로봇 c++ [컴공과고씨] (0) | 2022.08.12 |
| 백준 14890 경사로 c++ [컴공과고씨] (0) | 2022.08.12 |