[BOJ 백준] 13913번 : 숨바꼭질4 (Python, 파이썬)

www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

기본적인 BFS에 방문했던 경로를 따로 저장하여 경로를 역순으로 탐색하는게 추가된 문제였다.

 

 

수빈이가 갈 수 있는 3가지 경로을 모두 큐에 같이 저장하고 해당 경로마다 탐색을하면 분명 시간초과 또는 메모리 초과가 발생할 것이다.

 

 

기본적으로 수빈이가 이미 갔던 경로는 파악하기 위해서는 bool 타입의 visited 배열로 단순히 방문체크만 해주는 것에 한가지를 더 추가해야한다.

 

 

핵심은 현재 위치에 오기 직전 단계에서 갔던 곳을 별도의 리스트에 기록해주는 것이다.

• visited[현재 수빈이의 위치] = 바로 이전의 수빈이의 위치

 

그 후, 동생을 찾으면 visited 배열을 거꾸로 올라가며 수빈이가 방문했던 지점을 path 리스트에 추가해준다

output은 시작점 -> 도착점의 순서로 출력해야 하므로 path 리스트를 역순으로 출력해준다.

 

 

소스코드

  from collections import deque
  import sys

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

  visited = [-1]*100001 # 방문여부까지 확인하기 위해 -1로 초기화
  path = [] # 지금까지 방문 경로 저장
  def bfs(start, target):
      queue = deque() 
      queue.append((n,0))
      visited[start] = start
      while queue:
          cur, cur_time = queue.popleft()        
          if cur == target:  # 동생을 찾음
              idx = cur
              while idx != start:
                  path.append(idx)
                  idx = visited[idx] # 이 부분이 중요!
              path.append(start) # 첫 시작점까지 넣는다
              return cur_time
          if cur+1 < 100001 and visited[cur+1] == -1 :
              queue.append((cur+1,cur_time+1))
              visited[cur+1] = cur

          if cur-1 >= 0 and visited[cur-1] == -1 :
              queue.append((cur-1,cur_time+1))
              visited[cur-1] = cur

          if cur*2 < 100001 and visited[cur*2] == -1 :
              queue.append((cur*2,cur_time+1))
              visited[cur*2] = cur


  print(bfs(n,k))
  print(*path[::-1]) # 뒤에서 부터 출력