[Algorithm] 백준 1697 : 숨바꼭질

문제
https://www.acmicpc.net/problem/1697
풀이
https://github.com/nowChae/algorithm/blob/master/%EB%B0%B1%EC%A4%80/Silver/1697.%E2%80%85%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88/%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%88.py

수빈이가 동생을 찾는 가장 '빠른' 시간을 찾는 문제라는 것을 보고 bfs를 사용해야하는 문제이구나 라고 생각했다. 맨 처음 큐에 수빈이의 위치를 넣고 큐에서 빠지는 값을에 -1, +1, X2 한 값을 하나씩 큐에 넣는다. 이때 큐에서 값을 하나씩 뺄 때 동생의 위치와 일치하는 값이 빠진다면 그때의 시간을 출력하면 되겠다고 생각했다.

단순하게 처음엔 queue에 -1, +1, X2한 값과 그때의 시간을 각각 모두 넣어서 구현하도록 했더니 이미 넣었던 값들이 여러번 중복적으로 큐에 들어가게 되고, 그럼 시간도 증가할 뿐만 아니라 메모리 사용에서 초과가 발생했다. 이 이유는 bfs를 사용하지 않고 그냥 단순히 큐만 사용해서 풀려고 했기 때문이었다.

그래서 visited라는 리스트를 생성하여 한 번 방문한 위치는 큐에 넣지 않도록 수정해 주었다. 이때 visited 리스트의 크기를 어느정도로 선언해주어야 하는 고민이 생겼는데, 이 문제의 경우 입력 받는 수빈이의 점, 동생의 점이 모두 0 이상 100000이하 였기에 visited의 크기를 100001로 설정해주었다. 그리고 큐에 값을 넣을 때는 0 미만 100000 초과인 경우에는 아무 동작도 하지 않도록 수정해 주었다.

풀이 코드 1의 경우는 점의 위치와 그때의 시간을 모두 큐에 넣어서 관리해주었고,
풀이 코드 2의 경우에는 visited 리스트에 그 해당 위치에 방문할 때의 시간을 저장하도록 해주었다.

이해를 위해 그림을 간단하게 그려보면 아래와 같다.

< 풀이 코드 - 메모리 초과 >

# 메모리 초과 코드

import sys
from collections import deque

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

queue = deque([N, 0])

while True:
  cur = queue.popleft()
  sec = queue.popleft()

  if cur == K:
    print(sec)
    break
  else:
    queue.append(cur-1)
    queue.append(sec+1)
    queue.append(cur+1)
    queue.append(sec+1)
    queue.append(cur*2)
    queue.append(sec+1)

< 풀이 코드 1 - 수정 후 >

import sys
from collections import deque

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

visited = [False]*(100001) # 움직일 수 있는 최대 좌표
queue = deque([N, 0])
visited[N] = True
while True:
  cur = queue.popleft()
  sec = queue.popleft()

  if cur == K:
    print(sec)
    break
  else:
    if cur - 1 >= 0:
      if not visited[cur-1]:
        queue.append(cur-1)
        queue.append(sec+1)
        visited[cur-1] = True
    if cur + 1 <= 100000:
      if not visited[cur+1]:
        queue.append(cur+1)
        queue.append(sec+1)
        visited[cur+1] = True
    if cur * 2 <= 100000:  
      if not visited[cur*2]:
        queue.append(cur*2)
        queue.append(sec+1)
        visited[cur*2] = True

< 풀이 코드 2 - 수정 후 >

import sys
from collections import deque

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

visited = [0]*(100001) # 움직일 수 있는 최대 좌표 - 도착 시 시간 저장
queue = deque([N])

while queue:
  cur = queue.popleft()

  if cur == K:
    print(visited[cur])
    break

  for i in (cur-1, cur+1, cur*2):
    if 0 <= i and i <= 100000 and (not visited[i]):
      queue.append(i)
      visited[i] = visited[cur] + 1