[Algorithm] 13931. 숨바꼭질 4

13913: 숨바꼭질 4

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

• 문제 티어 : G4
• 풀이 여부 : Failed → Solved
• 소요 시간 : 26:28

정답 코드

시간복잡도 : O(V+E) ⇒ O(V + 3V) ⇒ O(4V)

• worst V : 200001
• worst E : 3 * 200001

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
visited = [False] * 200001
parents = [-1] * 100001 # 부모노드 기록(역추적으로 사용)

def bfs(x):
  dq = deque([x]) # 현재 위치
  visited[x] = True

  while dq:
    x = dq.popleft()
    if x == K:
      break

    for nx in (x-1, x+1, 2*x):
      if not visited[nx] and 0 <= nx <= 100000:
        dq.append(nx)
        visited[nx] = True
        parents[nx] = x # nx도착 이전 노드가 x임을 기록

def make_path(N, K, parents):
  path = []
  while K != N: # 시작 지점 N에 도달하기까지 역추적
    path.append(K)
    K = parents[K] # K의 부모 지점으로 이동
  path.append(N) # 최종으로 시작 지점 추가
  return list(reversed(path))

bfs(N)
path = make_path(N, K, parents)
print(len(path) - 1)
print(*path)

접근 방식

1. 부모 노드를 기록하며 역추적으로 경로를 파악하는 방법

아래 첨부한 잘못된 접근 방식에서, deque에 원소를 추가할 때 경로를 바로 넣어주는 것이 아니라,

deque에서 추출한 x의 다음 노드가 될 nx를 순회하면서,

parents[nx] = x

위와 같이 nx 노드로 도착하기 이전의 노드가 x였음을, 즉 부모노드를 배열에 기록해준다.

이 때 parents 배열은 N의 최댓값인 100000(메모리 초과 방지를 위해 100001로 초기화)로 크기를 지정해줬다.

1. visited의 범위 수정

내 로컬 환경에서 문제를 풀었을 때는 분명 정답이 나오는데, 백준 채점 결과 런타임 에러가 났다.

그 이유는 visited의 범위를 100001로 초기화해뒀기 떄문.

N이 이동할 수 있는 방법이 x-1, x+1이라면 100001로 visited의 범위를 초기화해도 무방하지만,

만약 N이 다음 노드로 2*x를 선택했을 때 최악의 경우 200000의 값을 가질 수 있다.

따라서 visited의 범위를 200001로 초기화해줬더니 맞았다.

1. parents를 통한 경로 역추적

def make_path(N, K, parents):
  path = []
  while K != N: # 시작 지점 N에 도달하기까지 역추적
    path.append(K)
    K = parents[K] # K의 부모 지점으로 이동
  path.append(N) # 최종으로 시작 지점 추가
  return list(reversed(path))

bfs 함수에서 parents 배열의 값을 넣어준 방식을 보자면, K부터 N까지의 경로가 역순으로 저장되어 있다.

그말인 즉슨 K를 시작으로 K = parents[K] 를 통해 K의 부모 지점으로 이동하면서 경로를 찾을 수 있다는 점이다.

문제 출력에서 요구한 시작값 N과 종료값 K를 path에 추가한 뒤, 역순으로 리턴하면 이동 경로가 나온다.

잘못된 접근 방식(+ 코드)

처음에는 BFS를 통해 deque 내부의 원소를 추가하면서

1. 시작 노드를 저장할 때
2. 덱에 다음 노드를 추가할 때

이렇게 두 번 path에 값을 갱신해줬다.

그 결과 소요 시간은 정답과 일치하게 나왔지만, path가 아주 이상하게 나왔다.

(다시 생각해보면 너무 당연한 결과다… BFS로 x-1, x+1, 2*x를 돌며 모두 path에 추가했으니까)

import sys
from collections import deque
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())
visited = [False] * 100001

def bfs(x):
  dq = deque([(x, 0)]) # 현재 위치, 이동 횟수
  path = []

  visited[x] = True
  path.append(x) # 경로 저장

  while dq:
    x, move = dq.popleft()
    if x == K:
      return move, path

    for i in (x-1, x+1, 2*x):
      if not visited[i]:
        dq.append((i, move+1))
        path.append(i)
        visited[i] = True

move, path = bfs(N)
print(move)
print(*path)

배운점 또는 느낀점

백준에 있는 숨바꼭질 문제 세트를 풀어보면서, 정말 조금씩 다른 문제에도 풀이 방법이 많이 차이남을 느꼈다.

기본 BFS를 잘 활용하는 방법을 배운 문제다!