[BOJ] [Python] 1697번 : 숨바꼭질

트리

 

BFS를 이용해서 풀었다.

 

li 리스트에는 방문할 위치를 차례대로 넣고, 방문하면 제거한다.

그리고 dp 리스트를 이용해서, 방문했던 위치는 재방문하지 않는다.

 

 

수빈이가 동생을 찾기까지 신경 쓴 것

 

1. 0 <= N <= 100,000 범위 내에서 움직인다.

이 범위를 벗어나지 않는다. 왜냐하면 수빈이와 동생이 모두 100,000 범위 내에서 시작하기 때문이다.

 

 

2. 최소 시간을 찾아야 한다.

BFS로 돌다 보면, 중복된 숫자가 생겨서 더 시간이 오래 걸리는 대도 불구하고 값이 갱신된다.

 

위 사진에 있는 예시로 이해해보면, 앞에서 나온 9의 dp가 1로 갱신되기 전에 9가 또 나오기 때문에

9는 li 리스트에 추가된다. 그리고 기존의 3초를 제치고 4초로 갱신된다.

 

그것을 막기 위해 min함수를 이용했다.

 

 

# 수빈, 동생 : 0 <= N <= 100,000
# 수빈 : x += 1 or x -= 1
# 수빈 : 2 * x

def find_out(start, target):
    dp = [0] * 100001
    count = [100000] * 100001

    count[start] = 0
    li = [start]

    while True:
        now = li[0]

        if dp[now] != 1:
            if now == target:
                return count[now]

            if 0 <= now - 1 <= 100000:
                li.append(now - 1)
                count[now - 1] = min(count[now - 1], count[now] + 1)

            if 0 <= now + 1 <= 100000:
                li.append(now + 1)
                count[now + 1] = min(count[now + 1], count[now] + 1)

            if 0 <= now * 2 <= 100000:
                li.append(now * 2)
                count[now * 2] = min(count[now * 2], count[now] + 1)

            dp[now] = 1

        li.pop(0)


l = list(map(int, input().split()))
print(find_out(l[0], l[1]))

 

 

 

 

비슷한 로직의 if문을 3번 사용했었는데, for문 추가하니 간단해졌다.

 

# 수빈, 동생 : 0 <= N <= 100,000
# 수빈 : x += 1 or x -= 1
# 수빈 : 2 * x

def find_out(start, target):
    dp = [0] * 100001
    count = [100000] * 100001

    count[start] = 0
    li = [start]

    while True:
        now = li[0]

        if dp[now] != 1:
            if now == target:
                return count[now]

            for n in now - 1, now + 1, now * 2:
                
                if 0 <= n <= 100000:
                    li.append(n)
                    count[n] = min(count[n], count[now] + 1)

            dp[now] = 1

        li.pop(0)


l = list(map(int, input().split()))
print(find_out(l[0], l[1]))