[백준/파이썬] 27211번 도넛 행성

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

27211번: 도넛 행성

조금 지저분하게 푼 것 양해바랍니다,,

 

우선, 보드의 크기와 입력은 고정되어있으므로 선언해준 뒤 시작한다. 이때 10x10 이라고 무조건 2차원 배열로 만들 필요는 없다! 

주사위는 +1 ~ +6까지 무조건 양의 방향으로만 증가하므로 1차원 배열로 선언해주어야 더 쉽게 풀 수 있다.

 

사다리와 뱀의 정보도 구별 지을 필요 없다. 어찌됐건 둘 다 만나면 다른 곳으로 이동하므로 하나의 리스트에 "이동 정보" 를 모두 저장해주었다. 

 

그리고 보드의 인덱스 하나에는 하나의 값이 아닌, [현재 위치, 만약 사다리나 뱀이 있다면 이동할 위치] 를 쌍으로 저장해주었다.

 

이제 bfs를 돌면 된다. bfs의 기본적인 틀에서 크게 벗어나는 것은 없다. 그저 jump할 곳이 있다면 그곳으로 jump 해주면 된다.

import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

board = [0] + [ [i,0] for i in range(1,101)]
num = 1
ladder = []
visited = [False for _ in range(101)]

dx = [1,2,3,4,5,6]

def bfs():
  q = deque()
  q.append([1,0])
  visited[1] = True
  cnt = 0
  
  while q:
    x = q.popleft()
    cnt = x[1]
    
    if x[0] == 100:
      return cnt

    for i in range(len(dx)):
      nx = x[0] + dx[i]
      
      if nx > 100: continue
      jump = int(board[nx][1])
 
      if jump != 0 and not visited[jump]:
        q.append([jump,cnt+1])
        visited[jump]= True

      elif jump == 0 and not visited[nx]:
        q.append([nx,cnt+1])
        visited[nx]= True

n,m = map(int,input().split())

for i in range(n+m):
  x,y = map(int,input().split())
  ladder.append([x,y])
  
for i in range(1,101):
    for j in range(n+m):
      if ladder[j][0] == board[i][0]:
        board[i] = [num,ladder[j][1]]
        
print(bfs())