1697번 - 숨바꼭질

시간제한 : 2초
메모리 제한 : 128MB

---

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

---

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

---

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

---

예제 입력 1

5 17

---

예제 출력 1

4

---

힌트

수빈이가 5-10-9-18-17 순으로 가면 4초만에 동생을 찾을 수 있다.

---

코드

import sys
from collections import deque

N, K= map(int, sys.stdin.readline().strip().split())  # N, K 입력

Q = deque() # Q 생성
Q.append(N) # 수빈이 위치(N)를 큐에 삽입

sec = 0 # 수빈이가 동생을 찾는 시간
flag = True # 동생을 찾았다면 while문을 종료할 변수
ch = [0]  * 100001  # 한 번 방문한 위치라면 제외하기 위한 리스트

while flag: # 동생을 찾기 전까지 반복
  # 현재 큐에 있는 위치(X)들을 기준으로 X-1, X+1, 2*X을 이동해 큐의 끝에 삽입
  length = len(Q)

  # 큐의 길이(큐에 저장된 위치의 개수)만큼 반복
  for _ in range(length):
    x = Q.popleft() # 큐에 있는 위치 중 하나 꺼내기
    if x == K:  # 큐에서 꺼낸 위치가 동생의 위치와 동일하냐?
      print(sec)  # 그렇다면 현재까지의 시간을 출력
      flag = False  # 찾았다고 flag에 전달
      break # for문 종료
    
    # 이동할 수 있는 경우의 위치들을 큐에 삽입
    for nx in [x-1, x+1, 2*x]:
      # 아래 if문을 하지 않는다면 메모리초과로 오류
      if 0 <= nx and nx <= 100000 and ch[nx] == 0:    # 현재 위치가 범위 밖이거나, 이미 방문한 위치라면 큐에 삽입 X
        Q.append(nx)  # 큐에 삽입
        ch[nx] = 1    # 방문했다고 표시
  # 현재 큐에 있던 위치들이 동생의 위치와 동일하지 않다면 sec + 1
  sec += 1

---

풀이

시간 : 176ms
메모리 : 34112KB

이 문제는 간단한 BFS 알고리즘 구현 문제이지만, 단순하게 풀었을 땐 메모리 초과나 런타임 오류가 발생할 수 있다.
따라서 BFS를 구현하되, 조건을 잘 설정해야한다.

먼저 N, K를 입력받고 Q를 생성해 수빈이의 위치 N을 삽입한다.
그리고 동생을 찾는 시간 sec, while문을 종료할 기준인 flag와 한 번 방문한 위치를 제외할 ch 리스트를 생성한다.

이제 BFS를 시작해보자
while문은 flag가 False인 경우 즉, 동생을 찾으면 종료한다.
for문은 현재 큐에 들어있는 개수만큼 반복한다.
for문이 시작되면 큐에 가장 앞에 있는 요소(위치)인 x를 꺼내 동생의 위치와 동일한지 확인한다.

• 동일한 경우 : 수빈이의 위치에서 동생 위치까지의 소요 시간 sec을 출력하고, flag를 False로 설정해 찾았다고 while문에게 알려주고 break를 통해for문을 종료한다.
• 동일하지 않은 경우 : 이동할 수 있는 경우의 위치인 [x-1, x+1, 2*x]를 큐에 삽입한다.
  이때, if문을 통해 현재 위치가 문제에서 알려준 범위를 벗어나지 않고, 이미 방문하지 않았는지 확인해 메모리초과 등의 문제를 예방한다.

for문의 반복이 끝났을 때도 찾지 못했다면 해당 시간에서는 동생의 위치까지 도달하지 못한 것이므로 sec += 1해준다.