[파이썬] 백준 16928 : 뱀과 사다리 게임 (골드5)

[파이썬] 백준 16928 : 뱀과 사다리 게임 (골드5)

 

16928번: 뱀과 사다리 게임

---

문제

# 출력 예제

# 4 9 --> 5
# 8 52
# 6 80
# 26 42
# 2 72
# 51 19
# 39 11
# 37 29
# 81 3
# 59 5
# 79 23
# 53 7
# 43 33
# 77 21

# 1 1 --> 3
# 13 99
# 8 7

# 1 5 --> 4
# 2 92
# 94 3
# 95 4
# 96 5
# 97 6
# 98 7

---

풀이

0. 방향성 생각

시점, 방문체크를 할 리스트를 만들어주고 BFS 탐색 시작.

문제 조건에 한 칸에는 사다리가 있거나, 뱀 있거나, 없거나 3가지.

두개 이상의 사다리, 뱀, 같이있는 경우는 없다

1. 입력 받기

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

a,b = map(int,input().split())
ladder,snake = {},{}

for i in range(a+b):
    start,end = map(int,input().split())
    if i<a :
        ladder[start] = end
    else :
        snake[start] = end

visit,time = [False]*101,[-1]*101

q = deque()
q.append(1)
visit[1],time[1] = True,0

딕셔너리에 사다리, 뱀의 위치를 저장. 시작->끝 형태로 저장한다.

 

2. BFS

while q:
    x = q.popleft()
    if x==100:
        break
    
    for nx in range(x+1,x+7):
        if 1<=nx<=100:
            
            if nx in ladder:
                nx = ladder[nx]
            elif nx in snake:
                nx = snake[nx]
             
            if not visit[nx]:
                visit[nx] = True
                time[nx] = time[x] + 1
                q.append(nx)
print(time[100])

pop해서 x==100이면 100에 탐색이 끝난것이므로 탈출

사다리, 뱀이 위치한 노드는 강제로 연결된 노드로 이동한다. 만났을 경우에는 nx를 이동한 경로로 이동해준다.

방문하지 않는 노드일 경우에 방문처리 해주고 현재 시간 +1 해준다.

---

전체코드

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

a,b = map(int,input().split())
ladder,snake = {},{}

for i in range(a+b):
    start,end = map(int,input().split())
    if i<a :
        ladder[start] = end
    else :
        snake[start] = end

visit,time = [False]*101,[-1]*101

q = deque()
q.append(1)
visit[1],time[1] = True,0

while q:
    x = q.popleft()
    if x==100:
        break
    
    for nx in range(x+1,x+7):
        if 1<=nx<=100:
            
            if nx in ladder:
                nx = ladder[nx]
            elif nx in snake:
                nx = snake[nx]
             
            if not visit[nx]:
                visit[nx] = True
                time[nx] = time[x] + 1
                q.append(nx)
print(time[100])

 

코멘트

사다리, 뱀 위치를 방문처리 한 경우로 먼저 풀었는데 처리조건이 늘어나서 방문처리하지 않고 풀었다.

1 1, 13 98, 8 7 같은 경우에 7번노드에서 꼬인다.

순방향이면 오류가 발생하지 않는데 뱀처럼 역방향으로 오는 경우가 있어서 도착지점에서만 방문처리를 한다