백준 17071 [숨바꼭질 5] 파이썬

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

 

어려웠다. 동생과 수빈의 도착 시간 차이가 짝수만큼 차이나면 결국 만날 수 있기에, 특정지점에 홀수 도착시간과 짝수도착시간을 분리하여 계산하는것이 핵심이었다.

from collections import deque

# 수빈이(N)와 동생(K) 위치 입력
N, K = map(int, input().split())

def search(subin, sister):
    cnt = 0  # 시간 (이동 횟수)
    q = deque()
    q.append((subin, sister, cnt, 2))  # (수빈 위치, 동생 위치, 시간, 짝/홀 여부)
    
    # 방문 여부 및 방문 시간 저장 배열
    # visited[i] = [짝수 방문 여부, 짝수 방문 시간, 홀수 방문 여부, 홀수 방문 시간]
    visited = [[False, 0, False, 0] for _ in range(500001)]
    
    visited[subin][2] = True  # 시작 위치 방문 체크
    
    while q:
        subin, sister, cnt, odd_even = q.popleft()
        
        # 동생의 위치가 이전에 방문한 적이 있고, 이동 횟수 차이가 짝수이면 잡을 수 있음
        if visited[sister][odd_even] and (cnt - visited[sister][odd_even + 1]) % 2 == 0:
            return cnt

        # 짝수/홀수 이동 상태 변경
        odd_even = 0 if odd_even else 2
        cnt += 1
        sister += cnt  # 동생은 cnt만큼 증가 (1+2+3+...)

        if sister > 500000:  # 범위를 벗어나면 continue
            continue

        # 수빈이 이동 가능한 경우 체크 (앞으로, 뒤로, 순간이동)
        for next_subin in (subin + 1, subin - 1, subin * 2):
            if 0 <= next_subin <= 500000 and not visited[next_subin][odd_even]:
                visited[next_subin][odd_even] = True
                visited[next_subin][odd_even + 1] = cnt
                q.append((next_subin, sister, cnt, odd_even))

# 시작점과 목표점이 같다면 0 출력
if N == K:
    print(0)
else:
    result = search(N, K)
    print(result if result is not None else -1)  # 찾을 수 없으면 -1 출력