[Baekjoon] 1697번 숨바꼭질

문제

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

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

입력

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

출력

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

예제

Example 1:

Input: 
5 17
Output: 
4

조건

시간 제한 : 2초

메모리 제한 : 128 MB

풀이과정

내 풀이 1

from collections import deque
n, k = map(int,input().split())

q = deque()
q.append(n)

visited = [0]*100001

while(q):
    x = q.popleft()
    if x == k:
        print(visited[k])
        break
    for nx in (x+1, x-1, 2*x):
        print(nx)
        if 0 <= nx < 100001 and visited[nx] == 0:
            visited[nx] = visited[x] + 1
            q.append(nx)
    print(q)

구글링을 통해 많은 도움을 받은 코드.

내 풀이 2

from collections import deque
n, k = map(int,input().split())

result = 0
q = deque()
q.append(n)
case = len(q)
visited = [False]*100001
visited[n] = True

last = False
while(1):
    for _ in range(case):
        x = q.popleft()
        if x == k:
          last = True
          break
        for nx in (x+1, x-1, 2*x):
          if 0 <= nx < 100001 and visited[nx] == False:
              visited[nx] = True
              q.append(nx)
    case = len(q)
    if last == True:
      break
    result += 1


print(result)

기존 내 코드의 문제점을 찾고 고친 코드.

내 풀이 3

from collections import deque
n, k = map(int,input().split())

result = 0
move = deque()
move.append(n)
case = len(move)
visited = [False]*100001
visited[n] = True
last = False

if n == k:
    print(0)
else:
    while(1):
        for _ in range(case):
            x = move.popleft()
            nx = [x-1,x+1,2*x]
            if x-1 == k or x+1 == k or 2*x == k:
                last = True
                continue
            for i in nx:
                if i >= 0 and i <= 100000 and visited[i] == False:
                    visited[i] = True
                    move.append(i)
        result += 1
        case = len(move)
        if last == True:
            break
   
    print(result)

풀이 2와 비슷하지만 제일 처음으로 구상했던 코드를 고친 코드.

문제점

2가지 문제점이 있었다.

첫째로는, n과 k가 같을 때가 고려되지 않았다. 둘이 같다면 이동할 필요가 없어서 0이 되어야 한다. 검색하여 고친 풀이 1은 애초에 큐에서 나올 때 검사를 하기 때문에 이를 고려할 필요가 없다. 하지만 기존의 내 풀이는 x에서 -1,+1,*2를 하고 검사를 하기 때문에 위의 코드처럼 먼저 조건을 거든지 방식을 바꾸든지 해야만 했다.

둘째로는, 메모리의 문제이다. 기존의 코드가 맞다고 하더라도 방문한 수에 대해 검사하는 코드를 넣지 않아서 메모리 초과가 나왔을 것이다.

간단한 문제라고 생각해서 이렇게 고전한게 나 자신에 조금 실망스럽기도 하고 수많은 실패가 마음 아프기도 하지만, 그래도 혼자 힘으로 잘못된 점을 찾아냈다는 점에 감사한다. 이를 발판으로 더 성장해야 할 것이다.