BOJ.16928

#BOJ16928

BFS

조금 아는 사람이 제일 무섭다고 이 문항도 보자마자 역시 나야 BFS겠군 이라고 생각을 하였는데 이후에 점점 이상한 상상이 들기 시작했다. 만약 뱀이 항상 손해라면 이 문제의 해결은 아주아주 쉬워보인다. 하지만 뱀을 타고 갔더니 사다리가 99칸으로 가는 사다리가 있다면 이 문항은 그 부분은 혼란을 주기 쉬워보인다. 그리디처럼 해결해보려고 했지만 그 부분이 막혀서 다른 방법을 생각해보기로 하였다. 우선 그리디처럼 생각해서 해결했을 때의 코드이다. 이제 이 부분을 해결하기 위해서 무언가 BFS적인 사고가 필요하다고 생각하였다.

import sys
import time

N, M = map(int, sys.stdin.readline().split())

arr = [0 for _ in range(100)]
for _ in range(N + M):
   a, b = map(int, sys.stdin.readline().split())
   arr[a - 1] = b - 1
idx = 0
cnt = 0
while True:
   temp = []
   for i in range(1, 7):
       if idx + i >= 99:
           print(cnt + 1)
           exit()
       if arr[idx + i] == 0:
           temp.append(idx + i)
       else:
           temp.append(arr[idx + i])

   cnt += 1
   idx = max(temp)

으아악 모르겠다. 생각을 해보자. 뭔가 저 위의 틀에서 벗어나기가 힘들단 생각이 들어서 처음으로 돌아가려고 하였다. cnt 별로 위계를 구분한다고 생각하면 될 것 같아서 visited 배열을 추가하였고, 계속해서 타고 간다는 생각으로 문항을 해결하였다. 솔직히 생각 안나서 힌트를 좀 봤다. 조금 아는 사람이 제일 무섭다더니... 너무 어렵다 생각보다 ㅜ

import sys
from collections import deque
N, M = map(int, sys.stdin.readline().split())

arr = [0 for _ in range(100)]
ans = [0 for _ in range(100)]
visited = [False for _ in range(100)]
for _ in range(N + M):
    a, b = map(int, sys.stdin.readline().split())
    arr[a - 1] = b - 1
q = deque([0])
while q:
    idx = q.popleft()
    if idx == 99:
        print(ans[99])
        exit()
    for i in range(1, 7):
        temp = idx + i
        if temp <= 99 and not visited[temp]:
            if arr[temp] != 0:
                temp = arr[temp]
            if not visited[temp]:
                visited[temp] = True
                ans[temp] = ans[idx] + 1
                q.append(temp)