13460번: 구슬 탈출 2
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
보드 안에 두 개(R, B) 구슬이 있고, 최소 몇 번 만에 빨간 구슬을 구멍(O)을 통해 빼낼 수 있는지 출력하는 문제입니다.
만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력합니다.
음... 이 문제도 일단 처음 접근은 X, Y 보드에 최소 이동을 구하는 문제이니 너비우선탐색(BFS)을 생각해봤습니다.
다만 한 번에 한칸이 움직이는 것이 아닌 보드의 끝까지 이동을 하는 방식이며,
B는 구멍을 통해 나가면 안 되는 조건이 추가되었습니다.
이번엔 파이썬(Python)으로 문제를 풀어볼게요.
1. 먼저 입력을 받고, 구슬을 넣고 돌릴 보드 생성, 그리고 visit node를 구성합니다.
visit node에는 빨간 공의 x, y좌표 파란 공의 x, y 좌표를 위해 4차원으로 선언합니다.
|
1
2
3
4
|
n, m = map(int, input().split())
board = []
visit = [[[[False] * m for i in range(n)] for i in range(m)] for i in range(n)]
|
cs |
2. 그런 다음 움직일 dx, dy 좌표를 정의하고 board에 문제 입력을 받아줍니다.
그 후 BFS를 수행하기 위해서 파이썬에서 사용하는 deque를 사용해주고
q.append를 사용해서 빨간 공의 현재 좌표, 파란 공의 현재 좌표, 그다음 우리가 알고자 하는 빨간 공의
움직인 횟수를 넣어줍니다. 한 번은 반드시 움직이므로 1을 넣어주고 시작합니다.
그리고 BFS알고리즘을 만들어주면 되겠죠
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
t = list(input())
board.append(t)
for j in range(m):
if t[j] == "R":
rx, ry = i, j
if t[j] == "B":
bx, by = i, j
q = deque()
q.append([rx,ry,bx,by,1])
visit[rx][ry][bx][by] = True
bfs()
|
cs |
3. 공들이 움직이는 조건 move() 함수 만들어서 체크
이번 조건은 공이 보드에서 한 번에 한 칸 움직이는 것이 아닌 기울기를 이용해 벽 끝까지 도달하거나
O구멍에 빠지는 조건입니다. 따라서 벽끝까지 도달하거나 O구멍에 빠질 때까지 계속 이동시켜주어야겠죠
그리고 마지막으로 변수 c를 만들어 각 공들이 몇 칸을 움직였는지 체크해 줍니다.
만약 # . . . R . B# 였다면 이것을 왼쪽으로 기울였을 때, R공은 3칸, B공은 5칸 움직이게 되는 것이죠.
움직임 값을 이용해 R이 더 왼쪽에 있는지 B가 더 왼쪽에 있는지 확인을 할 수 있고, B의 좌표를
한 칸 오른쪽으로 밀어주면서 결과적으로
#R B . . . . .# 와 같은 배치로 바뀌어질 것입니다.
|
1
2
3
4
5
6
7
|
def move(nx,ny,dx,dy):
c=0
while board[nx][ny] !='O' and board[nx+dx][ny+dy] !='#':
nx += dx
ny += dy
c +=1
return nx,ny,c
|
cs |
4. BFS 알고리즘으로 결과 도출
q가 비워질 때까지 while문을 돌리고 q를 꺼내서 현재 좌표와 움직인 횟수를 저장합니다.
그 움직인 횟수가 10회 이상이면 while 문을 빠져나가 24번 라인의 print(-1)을 출력하고요.
그게 아니라면 4방향 좌표에 대한 for문을 돌리고
그 안에서 move() 함수를 만들어 공들이 움직일 수 있는지 구멍에 들어가는지 체크를 하게 됩니다.
움직일 수 있는 조건이면, 움직일 새로운 좌표를 정의합니다.
9번째 줄에서 만약 파란 공이 O구멍에 있지 않을 때,
10번처럼 빨간 공은 O구멍에 도달했다면 조건 성공이므로 그때의 cnt 값을 출력합니다.
그게 아니면, move () 함수를 통해 얻어 냈던 rc, bc 값을 확인해서 빨간공과 파란공의 좌표를
재배치 시켜줍니다.
그 후 visit 노드를 체크해서 방문한 적이 없다면 true를 넣어주고
그 다음 각 공의 좌표와 이동 횟수를 추가 해주면 이 알고리즘은 완성이 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
def bfs():
while q:
rx,ry,bx,by,cnt = q.popleft()
if cnt >10:
break
for i in range(4):
nrx,nry,rc = move(rx,ry,dx[i],dy[i])
nbx,nby,bc = move(bx,by,dx[i],dy[i])
if board[nbx][nby] !='O':
if board[nrx][nry] =='O':
print(cnt)
return
if nrx == nbx and nry == nby:
if rc > bc:
nrx -=dx[i]
nry -=dy[i]
else:
nbx -=dx[i]
nby -=dy[i]
if not visit[nrx][nry][nbx][nby] :
visit[nrx][nry][nbx][nby] = True
q.append([nrx,nry,nbx,nby,cnt+1])
print(-1)
|
cs |
다음은 소스코드 전체입니다.
|
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
|
from collections import deque
n, m = map(int, input().split())
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]
visit = [[[[False] * m for i in range(n)] for i in range(m)] for i in range(n)]
board = []
def move(nx,ny,dx,dy):
c=0
while board[nx][ny] !='O' and board[nx+dx][ny+dy] !='#':
nx += dx
ny += dy
c +=1
return nx,ny,c
def bfs():
while q:
rx,ry,bx,by,cnt = q.popleft()
if cnt >10:
break
for i in range(4):
nrx,nry,rc = move(rx,ry,dx[i],dy[i])
nbx,nby,bc = move(bx,by,dx[i],dy[i])
if board[nbx][nby] !='O':
if board[nrx][nry] =='O':
print(cnt)
return
if nrx == nbx and nry == nby:
if rc > bc:
nrx -=dx[i]
nry -=dy[i]
else:
nbx -=dx[i]
nby -=dy[i]
if not visit[nrx][nry][nbx][nby] :
visit[nrx][nry][nbx][nby] = True
q.append([nrx,nry,nbx,nby,cnt+1])
print(-1)
for i in range(n):
t = list(input())
board.append(t)
for j in range(m):
if t[j] == "R":
rx, ry = i, j
if t[j] == "B":
bx, by = i, j
q = deque()
q.append([rx,ry,bx,by,1])
visit[rx][ry][bx][by] = True
bfs()
|
cs |
도움이 되셨다면 구독 좋아요? 눌러주세요~
'코딩 탐구 > 삼성 코딩테스트' 카테고리의 다른 글
| 백준 17170 파이프 옮기기1 (0) | 2021.01.14 |
|---|
