12851. 숨바꼭질 2

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

이해

• N에서 K까지 가는 길을 완전탐색을 통해 해결
• 완전 탐색을 하면서 최소가 되는 시점에만 값을 변경, 이후 같은 값이 나오면 카운트 ++

구현

1. 방문 확인용 배열 및 후보 과정을 담을 배열 생성
2. 만약 N == K인 경우 최솟값을 저장하고 다음 과정을 수행
3. 만약 N != K인 경우 다음 경로로 갈 수 있는 곳을 탐색하여 후보 과정 배열에 추가

코드

# 46944KB	380ms
# 12851 숨바꼭질 2
import sys
from collections import deque
input = sys.stdin.readline


def solution():
    N, K = map(int, input().split())
    que = deque([(0, N)])
    visited = [100000] * 100_001
    visited[N] = 0
    minv = 100_001
    c = 0
    while que:
        cnt, now = que.popleft()
        if now == K:
            if minv > cnt:
                minv = cnt
                c = 1
            elif minv == cnt:
                c += 1
        for next in [now+1, now-1, now<<1]:
            if 0 <= next <=100_000 and visited[next] >= visited[now]+1:
                visited[next] = visited[now] +1
                que.append((cnt+1, next))
    print(minv)
    print(c)

if __name__ == "__main__":
    solution()

느낀점

• 지난번 1697. 숨바꼭질에서 후보 과정을 배열에 담는 코드에서 반복문을 통해 더욱 간단히 넣는 방법을 찾았어서 적용해보았다. 확실이 조건문을 통해 코드를 작성하는 것보다 가독성과 작성 시간을 줄일 수 있었다.

2024.01.29 - [Algorithm/BaekJoon Review] - 1697. 숨바꼭질

1697. 숨바꼭질