100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 구하기.
입력 | 출력 |
---|---|
3 7 32 62 42 68 12 98 95 13 97 25 93 37 79 27 75 19 49 47 67 17 | 3 |
4 9 8 52 6 80 26 42 2 72 51 19 39 11 37 29 81 3 59 5 79 23 53 7 43 33 77 21 | 5 |
: bfs 이용. 사다리와 뱀에 대한 딕셔너리를 만들어 해당 수가 나왔을 때 대응하는 수로 이동하도록.
- 다음 움직임이 사다리이든 뱀이든 빈 칸이든 각각 병렬. 서로 관련 없음.
- 이동에 메리트가 있는게 아니므로(시간이 더 짧게 걸린다든가..) 똑같이 append.
from collections import deque
def bfs(ladder, snake, visited):
q = deque()
q.append(1)
visited[1] = 0
while q:
x = q.popleft()
if x==100:
print(visited[100])
return
for i in range(6, 0, -1):
move = x+i
if move <= 100:
if move in ladder and visited[ladder[move]] == -1:
visited[ladder[move]] = visited[x]+1
q.append(ladder[move])
if move not in ladder and move not in snake and visited[move] == -1:
visited[move] = visited[x]+1
q.append(move)
if move in snake and visited[snake[move]] == -1:
visited[snake[move]] = visited[x]+1
q.append(snake[move])
n, m = map(int, input().split())
ladder = {}
snake = {}
for _ in range(n):
s, e = map(int, input().split())
ladder[s] = e
for _ in range(m):
s, e = map(int, input().split())
snake[s] = e
visited = [-1]*101
bfs(ladder, snake, visited)