[BOJ][Python]16928번 풀이

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

16928번: 뱀과 사다리 게임

from collections import deque
import sys
ssr = sys.stdin.readline

n,m = map(int, ssr().split())
ls = [list(map(int, ssr().split())) for _ in range(n+m)]
visited = [0 for _ in range(101)]
q=deque([(1,0)])
visited[1] = 1
while q:
    tmp = q.popleft()
    if tmp[0] == 100:
        print(tmp[1])
        break
    for i in range(1,7):
        pos = tmp[0]+i
        if pos > 100:
            break
        else:
            for j in ls:
                if pos == j[0]:
                    pos = j[1]
                    break
            if visited[pos] == 0:
                q.append((pos, tmp[1]+1))
                visited[pos] = 1

문제를 보자마자 떠올렸던 건 예전에 풀었던 회의실 배정 문제였습니다. 그리디 알고리즘으로 정렬을 이용해서 푸는 문제였고, 해당 문제에도 같은 방법을 적용시킬 수 있지 않을까 해서 고민해봤는데 잘 안되더라구요. 근데 잘 생각해보니 뱀 때문에 그리디로 푸는 것 보다 그냥 100까지만 돌면 되니까 무작정 bfs를 돌리면 풀 수 있겠다 생각이 들었습니다(유사 브루트 포스?).

 

문제 접근은 bfs입니다. 일단 방문해야할 노드는 100개 밖에 안되고 간선도 많이 나와야 30개라서 방문처리하면서 넘기면 시간제한에 걸릴 일은 없는 문제가 되겠네요. 오히려 이차원이 아니라서 훨씬 직관적일지도 모르겠습니다. 주의하셔야 할 점은 뱀을 타는 경우가 더 빠를 수도 있다는 점일까요. 난이도가 높다기 보다는 놓칠수도 있는 부분들을 먼저 생각해보면 어렵지 않게 풀 수 있을 것 같습니다. 제가 사용했던 반례를 함께 첨부합니다.

 

1 1
13 99
7 2

답 : 4(6, 12, 13~99, 100)

 

2 1

2 97

98 3

4 99

답 : 2(2~97, 100)