파이썬 백준 16928번 : 뱀과 사다리 게임

문제 

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

 

 

🐍풀이

 최단경로문제로 BFS로 풀었다. 

 

import sys
from collections import deque

def find_road():
    queue=deque()
    queue.append((1,0))
    
    while(queue): #BFS 시작
        current_location,tries=queue.popleft()
        visited.add(current_location)

        if current_location>=100 :
            print(tries)
            break

        ladder_or_snakes=[] 
        for num_ladders in ladders: #사다리를 탈 수 있을 경우
            if current_location<num_ladders[0]<=current_location+6:
                x1,y1=num_ladders
                ladder_or_snakes.append(x1)
                if y1 not in visited:
                    queue.append((y1,tries+1))

        for num_snakes in snakes: #뱀을 탈 수 있는 경우 
            if current_location< num_snakes[0]<=current_location+6:
                x2,y2=num_snakes
                ladder_or_snakes.append(x2)
                if y2 not in visited:
                    queue.append((y2,tries+1))

        cnt=6 #사다리나 뱀을 타지 않고 이동
        while(cnt>0):
            if current_location+cnt not in ladder_or_snakes:
                if current_location+cnt not in visited:
                    queue.append((current_location+cnt,tries+1))

            cnt-=1

N,M=map(int,sys.stdin.readline().split())
result=0
ladders=[]
snakes=[]
visited=set()
for _ in range(N): # 사다리 리스트
    ladders.append(list(map(int,sys.stdin.readline().split())))
for _ in range(M): # 뱀 리스트
    snakes.append(list(map(int,sys.stdin.readline().split())))

find_road()

 

 

 

 

덧 1 ) 

훨씬 단순하게 풀 수 있을 것 같은데.. 처음에 틀려서 이것저것 추가하다가 코드가 지저분해졌다.

푼 기억이 휘발되면 다시 풀어봐야겠다. 

 

처음에 1%에서 계속 틀렸는데, 뱀과 사다리가 있는칸에는 무조건 뱀, 사다리를 타야한다

반례는 아래와 같다. 

2 1
2 60
35 98
65 30

#ans 4

 

덧 2)

visited를 안썼더니 메모리 오류가 발생했다. BFS시 visited쓰는 것 잊지말기!