[백준] 숨바꼭질5 17071번 - Python

문제

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

처음 아이디어 (실패)

• 1초마다 현재 시점에 수빈이가 있을 수 있는 곳 표시
• 동생 움직이고 수빈이와 같은 시간에 도착했는지 체크
• 시간초과함.. 수빈이가 갈 수 있는 곳이 3^n이라서 시간 지날수록 기하급수적으로 늘어서 그런듯..

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

time = 1
move = [0] * 500001
points = {N}

if N != K:
    while K < 500001:
        # 수빈 움직임 추가
        n_points = set()
        for subin in points:
            for nxt in (subin-1, subin+1, subin*2):
                if -1 < nxt < 500001:
                    move[nxt] = time
                    n_points.add(nxt)

        points = n_points

        # 동생 움직이고 잡혔는지 판단
        K += time
        if K < 500001 and time == move[K]:
            break

        time += 1
else:
    time = 0

if K < 500001:
    print(time)
else:
    print(-1)

참고 아이디어

https://dongchans.github.io/2019/53/
위 블로그의 해결방법 2번 참고

• 매 초마다 수빈이 방문할 수 있는 곳 체크
• 방문 한 적 없는 경우 현재 시간 저장. 현재 시간이 짝수인지 홀수인지에 따라 구분해서 저장(+1 -1로 다시 방문할 수 있기 때문에 최소시간만 저장)
• 수빈이가 이전에 이곳을 방문한 적이 있다면 동생 잡을 수 있는 것!

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

time = 1
move = [[-1, -1] for _ in range(500001)]  # 방문 시, 짝수, 홀수 최소 시간 저장
move[N][0] = 0
points = set([N])

if N != K:
    while K < 500001:
        # 수빈 움직임 추가
        n_points = set()
        for subin in points:
            for nxt in (subin-1, subin+1, subin*2):
                if -1 < nxt < 500001:
                    flag = time % 2
                    if move[nxt][flag] < 0:
                        move[nxt][flag] = time
                        n_points.add(nxt)

        points = n_points

        # 동생 움직이고 잡혔는지 판단
        K += time
        if K < 500001:
            flag = time % 2
            
            # 현재 시간에 동생 잡을 수 있는지 판단
            if move[K][flag] > -1:
                break           

            time += 1
else:
    time = 0

if K < 500001:
    print(time)
else:
    print(-1)