[알고리즘/BFS & DFS] 13913번 : 숨바꼭질 4 - python

링크 : https://www.acmicpc.net/problem/13913

13913번: 숨바꼭질 4

 

---

• 문제
• 소요시간 : 22분, 예외케이스 디버깅 1시간

---

• 설계하기(접근방법) 

1. 입력받기
숫자를 입력받는다

 

2. 구현하기

이중배열 혹은 리스트를 2개 선언해서 이전 경로를, 시간과 함께 담는다

 

그 후 end에 다다르면 경로를 역추척한다

역추적한 경로를 리스트에 담는다

 

 

3. 출력하기

역추적 경로 리스트를 뒤집어서 출력한다

 

---

• 코드(출력)

from collections import deque

def bfs(x,y):
    q = deque()
    q. append(x)
    while q: 
        x = q.popleft()
        if x == y:
            break
        for i in [x -1 ,x + 1, x * 2]:
            if 0<= i < 100001 and visited[i] == 0:
                visited[i] = visited[x] + 1
                visited_route[i] = x
                q.append(i)


start, end = map(int, input().split())
# 방문여부 = 시간, 이전 노드
visited = [0 for _ in range(100001)]
visited_route = [0 for _ in range(100001)]
visited[start] = 1

bfs(start, end)

print(visited[end] - 1)

route = []
current = end
while current != start:
    route.append(current)
    current = visited_route[current]
route.append(start)

print(*route[::-1])

---

• 얻어갈 부분

1. 예외 케이스인 start와 end가 같을 경우, print문에 출력할 route를 while문을 담는 과정에서 종료 조건을 제대로 설정하지 않아서 시간초과가 났다. 시간복잡도를 넘길일이 없는데 계속 시간초과가 나는 경우 while문이 잘못된것은 아닌지 의심해보자