백준 1697 숨바꼭질 Python ✔

✔ : 풀이참고. 다시 풀어야 봐야 할 문제 

문제설명

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

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

제한사항

• N(0 ≤ N ≤ 100,000)
• K(0 ≤ K ≤ 100,000)

입력

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

출력

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

예제

---

이 문제의 key포인트

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

예제를 보면 알 수 있듯이, 가장 빠른 시간이라고 동생의 위치에 가까워질 때까지 무작정 순간이동을 시키면 안된다.

EX ) N = 5, K = 17

무작정 순간이동: 5-10-20-19-18-17 -> 5초

정답: 5-10-9-18-17 -> 4초따라서 수빈이가 현재 있는 곳에서 갈 수 있는 지점을 모두 고려해야 한다. ->  BFS  사용

---

 자료구조 및 알고리즘: BFS + DP

---

문제풀이

첫번째 풀이

코드(틀린코드, 5%에서 메모리초과)

from collections import deque
N, K = map(int, input().split())
# 수빈이가 갈 수 있는 곳 다 찾기
queue = deque([])
def BFS():
    queue.append([N, 0]) # 수빈이 위치, 간 거리
    while queue:
        cur, cnt = queue.popleft()
        if cur == K: # 동생을 찾으면 중지
            print(cnt)
            break
        queue.append([2 * cur, cnt + 1]) # 순간이동
        queue.append([cur + 1, cnt + 1]) # 걷기
        queue.append([cur - 1, cnt + 1]) # 걷기

BFS()

수빈이가 현재 있는 곳이 5이면 수빈이가 갈 수 있는 곳은 [10, 6, 4] 이고

• 수빈이가 10으로 갔을 때 갈 수 있는 곳은 [20, 11, 9]
• 수빈이가 6으로 갔을 때 갈 수 있는 곳은 [12, 7, 5]
• 수빈이가 4로 갔을 때 갈 수 있는 곳은 [8, 5, 3]

이런 식으로 나뭇가지 모양으로 갈 수 있는 곳을 다 찾고 찾는 도중에 동생의 위치로 갔을 때 찾는 것을 중지하고 찾는데까지 걸린 시간을 출력하도록 하였다.

예제는 정답이 나왔지만 메모리초과가 났다. 

deque문제인가 싶어서 queue를 list로 바꾸고 popleft() 대신 pop(0)을 사용했더니 시간초과가 났다.

 

두번째 풀이

코드(완성코드, 맞았습니다!!, 152ms)

# BOJ 1697 숨바꼭질
# 152ms
# 34692KB

from collections import deque
N, K = map(int, input().split())
# 수빈이가 갈 수 있는 곳 다 찾기
queue = deque()
def BFS():
    queue.append(N) # 수빈이 위치
    while queue:
        cur = queue.popleft()
        # 동생위치 도착하면 함수 종료
        if cur == K: 
            return

        for i in (cur - 1, cur + 1, cur * 2):
            # 메모이제이션 
            if 0 <= i < 100001 and dp[i] == 0:
                dp[i] = dp[cur] + 1
                queue.append(i)

dp = [0] * 100001
BFS()
print(dp[K])

메모리를 줄이는 방법을 떠올리지 못해서 다른 사람의 풀이를 참고했다.

DP에서 사용하는 메모이제이션을 쓴 것 같다. 방문처리를 이용한거라고 해도 좋을 것 같다. 위의 코드와 아이디어는 동일하지만 이 코드에서는 if문을 이용해 노드가 중복된 곳을 또 가지 않도록 막아주었다. 내 생각보다 중복되는 노드로 많이 갔나보다..

 

그리고 for문을 리스트가 아니어도 for i in (cur - 1, cur + 1, cur * 2) 이렇게 쓸 수 있다는 것도 알게되었다!