1697 숨바꼭질 그래프

Kyung yup Lee·2021년 1월 31일
0

알고리즘

목록 보기
13/33

실1

bfs 문제로 나왔지만 memoization을 이용한 완전탐색 문제에 더 가까운 느낌이다.

얼핏 봤을 땐 이분탐색 문제인가 싶었다.

하지만 X가 이동하는 위치를 2배, +1, -1로 지정해주었고, count를 통해 몇 번만에 이동할 수 있는지 찾는 문제이므로 bfs로 풀었다.

먼저 memo를 통해 방문한 숫자를 방문처리해주지 않으면 메모리 초과가 뜬다.

queue 메모리구조에 너무 많은 숫자가 들어가 버리기 때문에.

때문에 dq에서 pop 시킨 배열을 temp, count로 만들어주고 해당 수에서 index가 허락하는 한, temp * 2, temp + 1, temp - 1 을 해주어 dq에 넣어준다.

그리고 한번 방문했던 숫자는 이미 해당 숫자에 대한 카운트가 처리되어 이미 dq에 들어가있다는 얘기이므로 방문처리를 해주어 dq에 넣지 않도록 한다.


from collections import deque

N, K = map(int, input().split(" "))
memo = [False for _ in range(100001)]

def solution():
    dq = deque([[N, 0]])

    while dq:
        temp, count = dq.popleft()
        memo[temp] = True

        if temp == K:
            print(count)
            return
        else:
            if temp * 2 < 100001:
                if not memo[temp*2]:
                    dq.append([temp * 2, count + 1])
            if temp - 1 >= 0:
                if not memo[temp-1]:
                    dq.append([temp - 1, count + 1])
            if temp + 1 < 100001:
                if not memo[temp+1]:
                    dq.append([temp + 1, count + 1])
    return


solution()
profile
성장하는 개발자

0개의 댓글