백준 1697 문제 풀이

🐒 숨바꼭질

https://www.acmicpc.net/problem/1697

✍ 나의 풀이

from collections import deque


N, K = map(int, input().split())

time = [0] * (10**5+1)

def bfs(n):
    queue = deque()
    queue.append(n)
    time[n] = 1
    while queue:
        x = queue.popleft()

        if x == K:
            return time[x]-1

        for i in [x-1,x+1,x*2]:
            if 0 <= i <= 10**5:
                if time[i] == 0:
                    queue.append(i)
                    time[i] = time[x] + 1

print(bfs(N))

전에 못풀고 답안 봤다가 재도전.

---

🧠 문제 이해

처음보고 그리디문제 아닌가,, 싶었는데
갈피도 못잡고 답지 봤다가 이해할 수 있었다.

최대입력인 0으로 채워진 10의 5승크기 배열을 만들어서 방문 처리를 하고,
bfs 함수에서 for문으로 x-1,x+1,x*2의 결과를 돌려서 탐색을 시키는게 신박했다.

나는 문제를 풀때 초기 위치가 0이니까 두번 탐색되는것을 막기 위해
시작위치에서 1로 시작했다가 탐색을 끝내고 -1을 해주고 출력하였는데,

생각해보니 이 과정이 없어도 정답에는 영향을 주지 않는것을 깨달알았다.
이 과정을 없애면 시간은 똑같은데 메모리 사용량이 증가한다??