반응형
알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
SOLUTION
import sys
from collections import deque
def bfs():
queue = deque([1]) # 보드게임의 시작은 1번 칸부터
while queue:
marker = queue.popleft()
# 주사위의 눈 1 ~ 6
for move in range(1,7):
move_marker = move + marker # 원래 위치에서 주사위의 눈 만큼 이동
if move_marker > 100: # 100을 넘으면 이동할 수 없으므로 패스
continue
num = game_board[move_marker] # 주사위를 던져서 이동한 위치의 칸
visited[num] # 이동한 칸은 방문처리
if visited[num] == 0: # 처음 방문 했다면
queue.append(num) # 도착한 칸을 다시 queue에 담음
visited[num] = visited[marker] + 1 # 원래 칸에서 주사위를 1회 던져서 이동한 칸이므로 +1
if num == 100: # 100번째 칸에 도달하면 종료
return
N, M = map(int, sys.stdin.readline().split())
game_board = [i for i in range(101)] # 게임보드판 형성
visited = [0] * 101 # 특정 칸까지 도달하기 위해 주사위 던진 횟수를 파악하기 위해 생성
for _ in range(N): # 사다리
x, y = map(int, sys.stdin.readline().split())
game_board[x] = y
for _ in range(M): # 뱀
u, v = map(int, sys.stdin.readline().split())
game_board[u] = v
bfs()
print(visited[100])
'코딩테스트 대비 > BOJ' 카테고리의 다른 글
[Baekjoon/Python] 5403번: AC - 효과는 굉장했다! (0) | 2022.03.09 |
---|---|
[Baekjoon/Python] 1107번: 리모컨 - 효과는 굉장했다! (0) | 2022.03.02 |
[Baekjoon/Python] 11403번: 경로 찾기 - 효과는 굉장했다! (0) | 2022.02.11 |
[Baekjoon/Python] 11286번: 절댓값 힙 - 효과는 굉장했다! (0) | 2022.02.11 |
[Baekjoon/Python] 6064번: 카잉 달력 - 효과는 굉장했다! (0) | 2022.02.11 |