[백준] 16928 뱀과 사다리 게임 (python 파이썬)

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

16928번: 뱀과 사다리 게임

---

아이디어

1. bfs

• 주사위를 선택(1 ~ 6)할 수 있는 점과 최단 횟수를 구해한다는 점에 bfs를 선택
• 뱀과 사다리만 잘 체크해주면 되는 문제.

---

코드 설명

    deq = deque()
    deq.append([1, 0])
    visited[1] = True

    while deq:
        po, count = deq.popleft()

        if po == 100:
            print(count)
            break

        for i in range(1,7):
            newpo = po + i
            if newpo > 100:
                continue

            for k in range(len(sadari)):
                if newpo == sadari[k][0] and not visited[newpo]:
                    visited[newpo] = True
                    deq.append([sadari[k][1], count + 1])

            for j in range(len(baaam)):
                if newpo == baaam[j][0] and not visited[newpo]:
                    visited[newpo] = True
                    deq.append([baaam[j][1], count + 1])

            if not visited[newpo]:
                visited[newpo] = True
                deq.append([newpo, count + 1])

bfs로 미로 찾기 할 때처럼 상하좌우 탐색 대신 주사위 1 ~ 6을 확인해주면 된다.

먼저 100을 넘어가면 안 되므로 100을 넘기면 continue로 넘겨준다. 이후 그 칸에 뱀이나 사다리가 있는지 확인해준다.

없다면 그냥 이동해주면 된다.

 

큐에는이동한 위치와 횟수를 추가해주면 된다.

최종적으로 위치가 100이 된다면 횟수를 출력해준다.

---

전체 코드

import sys
from collections import deque

def bfs():
    deq = deque()
    deq.append([1, 0])
    visited[1] = True

    while deq:
        po, count = deq.popleft()

        if po == 100:
            print(count)
            break

        for i in range(1,7):
            newpo = po + i
            if newpo > 100:
                continue
            
            for k in range(len(sadari)):
                if newpo == sadari[k][0] and not visited[newpo]:
                    visited[newpo] = True
                    deq.append([sadari[k][1], count + 1])

            for j in range(len(baaam)):
                if newpo == baaam[j][0] and not visited[newpo]:
                    visited[newpo] = True
                    deq.append([baaam[j][1], count + 1])

            if not visited[newpo]:
                visited[newpo] = True
                deq.append([newpo, count + 1])

if __name__ == '__main__':
    N, M = map(int, input().split())
    visited = [False for _ in range(101)]
    sadari = []
    baaam = []

    for i in range(N):
        sadari.append([int(x) for x in sys.stdin.readline().rstrip().split()])
    for i in range(M):
        baaam.append([int(x) for x in sys.stdin.readline().rstrip().split()])

    bfs()