13459번: 구슬 탈출
첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 전에 포스팅한 백준 알고리즘 13460번에서 10회 이하로 움직여서 구멍에 들어가는 것이 가능한 경우 횟수를 출력하는 것이 아닌 1을 출력, 불가능할 경우 -1을 출력하는 것이 아닌 0을 출력하는 것으로 하면 됩니다. 따라서 13460번 링크를 청부합니다.
백준 알고리즘 13460: 구슬 탈출 2 (Python)
www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열..
bgspro.tistory.com
소스코드
|
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(0)
return
if graph[rx][ry] == 'O': # 현재 빨간 구슬의 위치가 구멍이라면 count출력
print(1)
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(0) # 10회가 초과하지 않았지만 10회 내에도 구멍에 들어가지 못하는 경우
bfs(rx, ry, bx, by)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 1068: 트리(Python) (0) | 2021.02.21 |
|---|---|
| 백준 알고리즘 1074: Z(Python) (0) | 2021.02.20 |
| 백준 알고리즘 13460: 구슬 탈출 2 (Python) (1) | 2021.02.19 |
| 백준 알고리즘 9012: 괄호 (Python) (0) | 2021.02.06 |
| 백준 알고리즘 9095: 1, 2, 3 더하기(Python) (0) | 2021.02.06 |