코딩테스트 대비/BOJ

[Baekjoon/Python] 16928번: 뱀과 사다리 게임 - 효과는 굉장했다!

bluetag_boy 2022. 3. 2. 15:30
반응형
 

16928번: 뱀과 사다리 게임

첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으

www.acmicpc.net

 

알고리즘 분류

  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색

 

 

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])