[DFS/BFS/완전탐색] ▲ 13913번 - 숨바꼭질 4(BFS)

[백준] 13913번 - 숨바꼭질 4

풀이 시간: 60분 이내

유사 문제: 1697번, 12851번, 13549번

https://hseungyeon.tistory.com/222

[DFS/BFS/완전탐색] 1697번 - 숨바꼭질(BFS)

https://hseungyeon.tistory.com/229

[DFS/BFS/완전탐색] ★ 12851번 - 숨바꼭질 2(BFS)

https://hseungyeon.tistory.com/230

[DFS/BFS/완전탐색] ★ 13549번 - 숨바꼭질 3(BFS)

이 문제 역시 코드를 짜는 것 자체는 20분도 안걸렸으나 오류를 고치는데 시간이 많이 걸렸다.

숨바꼭질 문제들은 조금씩 모두 다른데 그 한 끝차이에서 구현해야할 방향이 조금씩 다르므로 모든 문제를 꼭 다시 풀어볼 필요가 있다.

(풀이1) 시간 초과된 실패 코드

1) 문제 해결 아이디어

이 문제는 시작, 끝 점이 주어졌을 때, 시작점에서 끝점까지 도달하기 위한 최소 시간과 최단 경로를 구하는 문제로 BFS로 구현한다. 이전 문제들과의 차이점은 최단 경로를 추가적으로 구해야하는 것이다.

 

그래서 기존에는 큐에 (현재 지점, 현재 시간)을 담았으나 이 문제의 경우 추가적으로 경로까지 담아 큐에 (현재 지점, 현재 시간, 방문 경로)를 담아 끝점(k)에 도달했을 때 큐에서 꺼낸 현재 시간(cnt)와 route(방문 경로)를 리턴하는 방식으로 생각하고 코드를 짰다.

 

첫번째 오류. 시간 초과

이 방식은 방문할 때마다 큐에 (현재 지점, 현재 시간, 방문 경로) 형태로 담는데 방문 경로(리스트)를 계속 담기 때문에 시간 초과가 나는 것 같다. 그래서 방문 경로를 계산하는 방식 자체를 바꾸어야할 필요가 있다.

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, cnt, route):
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, cnt, route))
  visited[x] = 1

  while queue:
    x, cnt, route = queue.popleft()
    
    # 끝점에 도달하면 종료
    if(x == k):
      return cnt, route
      
    for nx in [x - 1, x + 1, 2 * x]:
      if(0 <= nx <= 100000):
        if(visited[nx] == 0):
          # 삽입, 방문 처리
          queue.append((nx, cnt + 1, route + [nx]))          
          visited[nx] = 1
          
n, k = map(int, input().split())  # 시작점, 끝점
visited = [0] * (100001)
min_time, route = bfs(n, 0, [n])
print(min_time)
for r in route:
  print(r, end= " ")
#print(" ".join(map(str, route)))

 

(풀이2) 시간 초과를 해결한 정답 코드

1) 문제 해결 아이디어

<시간 초과를 해결하기 위한 방법>

원래 visited를 0으로 초기화하고 방문할 때마다 해당 값을 visited[nx] = 1 이런 식으로 항상 같은 값이 1로 초기화해주었다. 하지만 큐에 넣지않고 경로를 나중에 계산하기 위해서 방문 처리를 할 때 항상 같은 값(1)이 아닌 이전 값을 넣어 역순으로 경로를 계산할 수 있게 하였다.

 

1. visited를 -1로 초기화

2. 시작지점(n)의 방문 처리 값: 0 (시작 지점의 경우 이전 값이 없기 때문에)

3. 시작지점(n)을 제외한 모든 지점(nx)의 방문 처리 값: x (이전 값을 넣어주어야 나중에 도착지점에서부터 역순으로 경로를 탐색할 수 있음!!!)

4. 끝점(k)에 도달시, 최소 시간(cnt)만 리턴

5. 최단 경로의 크기(cnt + 1)만큼 for문을 돌며 역순으로 경로를 탐색하며 최단 경로(path)에 저장

6. 최단 경로(path) 역순으로 출력

 

예를 들어 5, 17이 입력으로 들어온다면 visited[: 18]는 다음과 같다. (편의상 0~17 인덱스 값만봄)

[1, 2, 3, 4, 5, 0, 5, 6, 4, 10, 5, 10, 6, 12, 7, 16, 8, 16]

17(끝점) 삽입, 17인덱스의 값 = 16

16 삽입, 16인덱스의 값 = 8

8 삽입, 8인덱스의 값 = 4

4 삽입, 4인덱스의 값 = 5

5 삽입, 5인덱스의 값 = 0

실제로 path에 들어온 값은 17, 16, 8, 4, 5 가 되고 실제 출력은 역순으로 해야 최단 방문 경로가 된다.

 

[참고] https://chul2-ing.tistory.com/64

[백준][파이썬] 13913번: 숨바꼭질4 - 근데 메모리 초과를 곁들인

 

2) 소스코드

from collections import deque

# BFS
def bfs(x, cnt):
  queue = deque()
  # 시작 지점 삽입, 방문 처리
  queue.append((x, cnt))
  visited[x] = 0  # 이전 방문값이 없음

  while queue:
    x, cnt = queue.popleft()
    
    # 끝점에 도달하면 종료
    if(x == k):
      return cnt  # 최소 시간 리턴
      
    for nx in [x - 1, x + 1, 2 * x]:
      if(0 <= nx <= 100000):
        # 방문한적이 없으면
        if(visited[nx] == -1):
          # 삽입, 방문 처리
          queue.append((nx, cnt + 1))    
          visited[nx] = x  # 이전 값 기록 
          
n, k = map(int, input().split())  # 시작점, 끝점
visited = [-1] * (100001)  # 방문 여부
min_time = bfs(n, 0)
path = [] # 최단 경로
print(min_time)

i = k  # 끝점으로 초기화
# 역순으로 경로 탐색 저장하기
for _ in range(min_time + 1):
  path.append(i)  
  i = visited[i]
# 경로 역순으로 출력하기
for i in range(min_time, -1, -1):
  print(path[i], end = " ")