12851: 숨바꼭질 2

문제 링크

12851: 숨바꼭질 2

구현 방식

• 처음에 dfs로 풀려 했는데 TLE 받음

• 가장 빠른 시간이 몇 초 후인지와, 가장 빠른 시간으로 찾는 방법이 몇 가지인지를 구해야하기 때문에 queue에 노드를 추가할 때 조건문을 조금 신경써줘야 한다

  • 1) 방문한 적 없는 경우와 2) 방문한 적 있는데 이동 시간이 같은 경우 모두 queue에 추가해줘야한다

• 한 가지 예외 처리 해줘야할 게 N >= K인 경우 -1로 가는 방법밖에 없기 때문에 먼저 print(N-K); print(-1) 해주고 프로세스를 종료시켜줬다

코드

import sys
from collections import deque

N, K = map(int, sys.stdin.readline()[:-1].split())

if N >= K:
    print(N-K); print(1); exit()

queue = deque([]); queue.append(N)
visit = [-1]*100001; visit[N] = 0

way_cnt = 0
while queue:
    curr = queue.popleft()
    if curr == K:
        way_cnt += 1
    for next in (curr-1, curr+1, curr*2):
        if 0 <= next <= 100000:
            if visit[next] == -1 or visit[next] == visit[curr]+1: # 1) 방문한적 없는 경우 2) 방문한적 있는데 이동 시간 같은 경우
                visit[next] = visit[curr] + 1
                queue.append(next)

print(visit[K])
print(way_cnt)