숨바꼭질(백준 13549번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가? ✓

---

난이도 체감

1. 최상

2. 상✓

3. 중

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

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

나의 풀이(정답 참고)

from collections import deque

N,K=map(int,input().split())
def BFS(N,K,visited):
    queue=deque()
    queue.append(N)
    visited[N]=0
    while queue:
        c=queue.popleft()
        if c==K:
            return visited[c]
        if 0<=c-1<=100000 and visited[c-1]==-1:
            queue.append(c-1)
            visited[c-1]=visited[c]+1
        if 0<=c*2<=100000 and visited[c*2]==-1:
            queue.appendleft(c*2)
            visited[c*2]=visited[c]
        if 0<=c+1<=100000 and visited[c+1]==-1:
            queue.append(c+1)
            visited[c+1]=visited[c]+1
visited=[-1]*100001
print(BFS(N,K,visited))

• 이런 선택지가 많은 문제들이 나오면 BFS를 먼저 떠올려보는 것도 좋은 방법인 것 같다.
• 처음 내가 풀었던 방식으로 했을 때 메모리 초과가 나왔다.
• queue에 위치와 몇번 연산되었는지 정보를 튜플 형태로 저장했는데, 이것이 원인이었다.
• visited를 유지하여, visited에 총 연산 횟수를 적어놓는다면 메모리 초과 없이 해결할 수 있었다.