[백준-16928] 뱀과 사다리게임

❓ Problem

문제링크

 

🤔 How

1. 그래프 탐색문제 로 분류되고 100칸에 가장 빨리가는경우를 찾는것이다.
2. 뱀과 사다리를 만날경우 반드시 이동한다

• 이점을 놓지기 쉬운데 뱀과 사다리를 만나서 visited 체크를 하고 넘기는 방법으로 접근한다면 뱀 (혹은 사다리) 시작지점에서 멈추는 경우도 계산해버리게 된다. (예를들어 2->16 으로가는 사다리가있다면 사실상 2번은 방문처리 할 수없다.)

❗ Solve

# 뱀과 사다리 게임

import sys
from collections import deque, defaultdict

input = sys.stdin.readline


def solution():
    global visited, board, snake_and_stair
    N, M = map(int, input().split())
    visited = [False] * 101
    board = [0] * 101
    snake_and_stair = defaultdict(
        int, {k: v for k, v in (map(int, input().split()) for _ in range(N + M))}
    )
    bfs(1)
    pass


def bfs(pos):
    q = deque([pos])
    visited[pos] = True  # 방문 여부를 저장
    board[pos] = 0  # 주사위 횟수를 저장
    while q:
        pos = q.popleft()
        if pos == 100:
            print(board[pos])
            break
        else:
            for dice in range(1, 7):
                next_pos = pos + dice
                if next_pos > 100 or visited[next_pos]:  # 방문 한경우 넘기기
                    continue
                if snake_and_stair[next_pos]:
                    next_pos = snake_and_stair[next_pos]  # 뱀,사다리 이동
                if visited[next_pos]:
                    continue
                board[next_pos] = board[pos] + 1
                visited[next_pos] = True
                q.append(next_pos)

                pass


if __name__ == "__main__":  # 실행되는 부분
    solution()
    pass