[백준/파이썬]16928 뱀과 사다리 게임

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

16928번: 뱀과 사다리 게임

문제

백준 16928번 뱀과 사다리 게임

구현 자체는 시간이 오래 걸리지 않았지만, 최적화할 때 질문 게시판에서 힌트를 얻었다.

 

자꾸 28%에서 시간 초과가 나왔었다.

 

문제는 1부터 시작해 100까지 갈 때, 주사위를 굴려서 간다.

 

그런데 뱀과 사다리가 있는데, 뱀은 현재 번호에서 뒤쪽으로 이동시키는 수단이고, 사다리는 현재 번호에서 앞쪽으로 이동시키는 수단이다.

 

뱀과 사다리의 위치와 각각 이동시키는 지점이 입력으로 주어 졌을 때, 1부터 시작해 100까지 주사위 굴리는 횟수를 최소로 하는 숫자를 찾는 문제다.

 

나는 이 문제를 풀기 위해서 뱀과 사다리의 위치와 이동 지점을 딕셔너리로 저장해 뒀다.

 

bfs탐색은 1부터 큐에 넣었고, 큐에서 하나씩 빼서, 1~6(주사위에서 나올 수 있는 경우의 수) 숫자를 더한 후, 뱀 혹은 사다리가 그 지점에 있는지 검사를 했고, 있다면 뱀 혹은 사다리를 이용해 이동한 지점을 큐에 저장, 없다면 그냥 더해진 수를 큐에 저장했다.

 

이렇게 반복하다가 현재 위치가 100이 됐을 때, 함수를 종료하고 카운트 횟수를 반환해 줬다.

 

이 구현 방법을 생각하고, 별생각 없이 코드를 짰다. 그리고 예제 입력 1, 2를 넣어봤는데 한 번에 예제 출력이 잘 나와줘서 당황했다. 한번에 이렇게 잘 나와준다고?

 

정답

from collections import deque
import sys

input = sys.stdin.readline

def bfs() :
    queue = deque()
    queue.append(1)
    visit[1] = 1
    c = 0
    while queue :
        for_len = len(queue)
        for _ in range(for_len) : # 깊이 측정을 위한 for문
            now = queue.popleft()
            if now == 100 :
                return c
            for i in range(1, 7) :
                next = now + i
                if next > 100 :
                    continue
                if visit[next] == 0 : # 한번 지났던 길은 다시 queue에 넣지 않음
                    if next in snakes :
                        queue.append(snakes[next])
                    elif next in ladders :
                        queue.append(ladders[next])
                    else :
                        queue.append(next)
                    visit[next] = 1
        c+=1

l, s = map(int, input().split())

snakes = {}
ladders = {}
visit = [0 for _ in range(101)]
for i in range(l) :
    x, y = map(int, input().split())
    ladders[x] = y

for i in range(s) : 
    x, y = map(int, input().split())
    snakes[x] = y
print(bfs())