[BOJ] (BFS) 16928번 뱀과 사다리게임

 

 

bfs로 푸는데, 100개의 점을 6번씩 루프 돌리면 연산량이 굉장히 많아진다. 

중간에 컷 할 필요가 느껴지는데, visited를 이용하면 된다. 

같은 곳을 또 방문하면, cnt만 늘어날 뿐더러, 뱀을 만나 내려오면 무한루프에 빠질 수 있기 때문이다. 

오랜만에 문제 푸는거라 감이 떨어졌다,...ㅎ

from collections import deque

def main():
    n, m = map(int, input().split())
    board = [[i, i] for i in range(101)]
    for _ in range(n+m):
        x, y = map(int, input().split())
        board[x] = [x, y]
    visited = [False] * 101
    
    q = deque([(1, 0)])
    while q:
        now, cnt = q.popleft()
        if now == 100:
            print(cnt)
            return
        
        for dice in range(1, 7):
            next = now + dice
            if next > 100: continue
            
            next = board[next][1]
            if visited[next]: continue
            
            visited[next] = True
            q.append((next, cnt+1))


main()

 

 

 

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