[BOJ][Python]12851 풀이

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

12851번: 숨바꼭질 2

from collections import deque

n, k = map(int, input().split())
visited = [0 for _ in range(200001)]
visited[n] = 1
q = deque([(n, 0)])
ans = 100001
methods = []
while q:
    cur_pos, cur_time = q.popleft()
    if cur_pos == k:
        methods.append(cur_time)
        if ans > cur_time:
            ans = cur_time
    else:
        dpos = [cur_pos-1, cur_pos+1, cur_pos*2]
        for i in dpos:
            if 0 <= i <= 200000 and visited[i] <= 3:
                q.append((i, cur_time+1))
                visited[i] += 1
print(ans)
print(methods.count(ans))

이런 비슷한 문제가 클래스 문제를 풀면서 올라오신 분들에게는 몇 번 풀었던 적이 있으실겁니다. 그래서 딱히 어려운 문제는 아니고 다른 문제들과 다른 점이라고 한다면 최소 시간을 내는 방법이 몇가지가 있는지를 체크해야하는 점이 차이랄까요. 이동 방법이 3가지니까 아무리 여러 경우가 있다고 해도 최대 3번 뿐일겁니다. 그래서 3번이 넘으면 중복이라고 생각하고 방문처리를 해줬습니다.

 

런타임이 짧은 분들 코드를 훑어보니까 조건문을 굉장히 타이트하게 작성해서 런타임을 줄이셨더라구요. 저는 그냥 기존에 하던 방법대로 풀어봤습니다.