[백준] 16928번 뱀과 사다리 게임 _ Python

https://www.acmicpc.net/problem/16928

16928번: 뱀과 사다리 게임

 

 

---

 

1. Preview

시간 복잡도: O(6*NM), bfs

 

공간 복잡도: O(NM)

 

유형: 그래프 탐색, bfs

 

 

---

 

2. 초기 접근 방법

visited[e] : 사다리

visited[nx] : 일반 주사위 길

2가지 경우 모두 queue에 삽입하여, 해당 경우를 고려해 탐색하게 된다.

for s, e in road:
    if s == nx and not visited[e]:
        visited[e] = visited[x] + 1
        q.append(e)

# 중복 방문 X
if not visited[nx]:
    visited[nx] = visited[x] + 1
    q.append(nx)

 

 

---

 

3. 생각

문제에서 요구하는 것은 뱀과 사다리를 만났을 때 선택해서 타거나, 타지 않는 것이 아니라 무조건 타는 것이다.

요구 사항을 정확히 파악하고 로직을 철저히 검증하자.

 

 

---

 

4. 코드

import sys
from collections import deque

input = sys.stdin.readline

# 사다리 수, 뱀 수
N, M = map(int, map(int, input().split()))

road = []
visited = [0] * 106
for _ in range(N + M):
    s, e = map(int, map(int, input().split()))
    road.append((s, e))

q = deque()
q.append(1)

while q:
    x = q.popleft()

    if x == 100:
        print(visited[100])
        exit()

    for i in range(1, 7):
        nx = x + i

        # 사다리나 뱀일 경우, 이용한다.
        for s, e in road:
            if nx == s:
                nx = e

        # 중복 방문 X
        if not visited[nx]:
            visited[nx] = visited[x] + 1
            q.append(nx)