13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 저는 BFS를 이용하여 해결하였습니다. 삼성 기출문제의 특성상 구현 즉 시뮬레이션 유형도 포함이 되어있는 문제였습니다. 고민을 많이 해결했던 문제지만 해결을 한 뒤에 생각해보면 그다지 어렵지는 않은 문제라 생각되기 때문에 구현 유형을 더 많이 공부해야겠다고 느낍니다.
먼저 그래프를 입력받을 때 빨간 구슬의 위치와 파란 구슬의 위치를 각각 rx, ry, bx, by로 지정해줍니다. 그 후 bfs를 수행하는데 먼저 rx, ry, bx, by를 큐에 넣어주고 방문처리를 해줍니다. 구슬이 한번 움직이면 멈추는 경우는 2가지입니다.
1. 움직인 곳이 벽 # 인 경우
2. 구멍인 경우
따라서 이 2가지인 경우를 제외하고는 계속 움직일 수 있으므로 while True를 이용해 움직여 줍니다. 단 1번의 경우 방향을 유지하면서 한 칸 뒤로 이동해야 구슬의 현재 위치가 벽이 아니겠죠.
이 과정을 빨간 구슬과 파란 구슬 모두 수행해줍니다. 단 파란 구슬이 구멍에 들어간 경우 2가지의 상황이 존재하는데
1. 빨간 구슬 파란 구슬 모두 구멍에 들어간 경우
2. 파란 구슬만 구멍에 들어간 경우
입니다. 그러나 이 2가지의 경우는 모두 문제에서 안된다고 조건이 있기 때문에 이 경우를 무시하기 위해 continue를 해줍니다. 그 외에 두 구슬이 같은 위치에 있다면 이 역시 문제에서 안 되는 조건이므로 더 많이 이동한 구슬 즉 더 늦게 이동한 구슬을 방향을 그대로 유지한 채로 한 칸 뒤로 움직여 줍니다.
소스코드
|
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
|
from collections import deque
import sys
input = sys.stdin.readline # 빠른 입출력 위한 코드
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(input()))
for j in range(m):
if graph[i][j] == 'R': # 빨간구슬 위치
rx, ry = i, j
elif graph[i][j] == 'B': # 파란구슬 위치
bx, by = i, j
# 상 하 좌 우로 탐색
dx = [-1, 1, 0, 0]
dy = [0, 0, -1 ,1]
def bfs(rx, ry, bx, by):
q = deque()
q.append((rx, ry, bx, by))
visited = [] # 방문여부를 판단하기 위한 리스트
visited.append((rx, ry, bx, by))
count = 0
while q:
for _ in range(len(q)):
rx, ry, bx, by = q.popleft()
if count > 10: # 움직인 횟수가 10회 초과면 -1 출력
print(-1)
return
if graph[rx][ry] == 'O': # 현재 빨간 구슬의 위치가 구멍이라면 count출력
print(count)
return
for i in range(4): # 4방향 탐색
nrx, nry = rx, ry
while True: # #일 때까지 혹은 구멍일 때까지 움직임
nrx += dx[i]
nry += dy[i]
if graph[nrx][nry] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
nrx -= dx[i]
nry -= dy[i]
break
if graph[nrx][nry] == 'O':
break
nbx, nby = bx, by
while True: # #일 때까지 혹은 구멍일 때까지 움직임
nbx += dx[i]
nby += dy[i]
if graph[nbx][nby] == '#': # 벽인 경우 왔던 방향 그대로 한칸 뒤로 이동
nbx -= dx[i]
nby -= dy[i]
break
if graph[nbx][nby] == 'O':
break
if graph[nbx][nby] == 'O': # 파란구슬이 먼저 구멍에 들어가거나 동시에 들어가면 안됨 따라서 이 경우 무시
continue
if nrx == nbx and nry == nby: # 두 구슬의 위치가 같다면
if abs(nrx - rx) + abs(nry - ry) > abs(nbx - bx) + abs(nby - by): # 더 많이 이동한 구슬이 더 늦게 이동한 구슬이므로 늦게 이동한 구슬 한칸 뒤로 이동
nrx -= dx[i]
nry -= dy[i]
else:
nbx -= dx[i]
nby -= dy[i]
if (nrx, nry, nbx, nby) not in visited: # 방문해본적이 없는 위치라면 새로 큐에 추가 후 방문 처리
q.append((nrx, nry, nbx, nby))
visited.append((nrx, nry, nbx, nby))
count += 1
print(-1) # 10회가 초과하지 않았지만 10회 내에도 구멍에 들어가지 못하는 경우
bfs(rx, ry, bx, by)
|
cs |
소스코드 - 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
|
#include <bits/stdc++.h>
#define MAX 11
using namespace std;
int n, m;
char graph[MAX][MAX];
int visited[MAX][MAX][MAX][MAX];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
int rx, ry, bx, by;
int bfs(int x1, int y1, int x2, int y2) {
queue<pair<int, int>> q1;
queue<pair<int, int>> q2;
q1.push(make_pair(x1, y1));
q2.push(make_pair(x2, y2));
visited[x1][y1][x2][y2] = 1;
int count = 0;
while (!q1.empty()) {
int len = q1.size();
for (int i = 0; i < len; i++) {
int rx = q1.front().first;
int ry = q1.front().second;
int bx = q2.front().first;
int by = q2.front().second;
q1.pop();
q2.pop();
for (int j = 0; j < 4; j++) {
int nrx = rx;
int nry = ry;
int nbx = bx;
int nby = by;
while (true) {
nrx = nrx + dx[j];
nry = nry + dy[j];
if (nrx < 0 || nry < 0 || nrx >= n || nry >= m) {
continue;
}
if (graph[nrx][nry] == '#') {
nrx = nrx - dx[j];
nry = nry - dy[j];
break;
}
else if (graph[nrx][nry] == 'O') {
break;
}
}
while (true) {
nbx = nbx + dx[j];
nby = nby + dy[j];
if (nbx < 0 || nby < 0 || nbx >= n || nby >= m) {
continue;
}
if (graph[nbx][nby] == '#') {
nbx = nbx - dx[j];
nby = nby - dy[j];
break;
}
else if (graph[nbx][nby] == 'O')
break;
}
if (graph[nbx][nby] == 'O') {
continue;
}
if (nrx == nbx && nry == nby) {
if (graph[nbx][nby] == 'O')
break;
else {
if (abs(rx - nrx) + abs(ry - nry) < abs(bx - nbx) + abs(by - nby)) {
nbx = nbx - dx[j];
nby = nby - dy[j];
}
else {
nrx = nrx - dx[j];
nry = nry - dy[j];
}
}
}
if (graph[nrx][nry] == 'O' && graph[nbx][nby] != 'O') {
if (count + 1 > 10)
continue;
return count + 1;
}
if (visited[nrx][nry][nbx][nby] == 0) {
visited[nrx][nry][nbx][nby] = 1;
q1.push(make_pair(nrx, nry));
q2.push(make_pair(nbx, nby));
}
}
}
count += 1;
}
if (count > 10) {
return -1;
}
return -1;
}
int main(void) {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> graph[i][j];
if (graph[i][j] == 'R') {
rx = i;
ry = j;
}
else if(graph[i][j] == 'B') {
bx = i;
by = j;
}
}
}
cout << bfs(rx, ry, bx, by);
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1074: Z(Python) (0) | 2021.02.20 |
|---|---|
| 백준 알고리즘 13459: 구슬 탈출(Python) (0) | 2021.02.19 |
| 백준 알고리즘 9012: 괄호 (Python) (0) | 2021.02.06 |
| 백준 알고리즘 9095: 1, 2, 3 더하기(Python) (0) | 2021.02.06 |
| 백준 알고리즘 2468: 안전 영역(Python) (2) | 2021.02.05 |