문제 링크

이번엔 숨바꼭질 시리즈입니다.

저는 이 문제를 풀다가 비슷한 또다른 접근이 생각나서 bfs식과 dijkstra식 접근을 해서 두번 풀게 되었는데요. 다양한 고민을 해볼 수 있는 문제라 재미있었습니다.

sol

제가 해봤던 시도들 중 처음 풀었던 방식입니다.
이 문제에서 주의할 것은 출력할 때 같습니다.

• 출력

  첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
  둘째 줄에는 가장 빠른 시간으로 수빈이가 동생을 찾는 방법의 수를 출력한다.

Bfs

0 ~ 100,000까지의 긴 x축에서, n에서 출발해 수빈이가 이동할 수 있는 방법은 3가지이죠. 이 때 모든 노드를 미방문 상태(-1)로 초기화 한 후 탐색을 시작합니다.
새로 방문한 노드(nx)에 기존 노드(vx)의 값 +1 을 해서 저장하며 탐색하면 목적지까지 알아서 최단시간으로 쓸 수 있는 값이 저장될 겁니다.

문제는 이 도착지점까지 한번만 방문하게 해서는 안된다는 겁니다. 원래라면 최단시간을 찾았으니 끝!이지만 이번 문제에서는 동일한 최단시간이 나오는 또다른 경우도 세어야 합니다. 따라서 모든 노드를 한번씩 방문해봐야 하겠습니다. 아래 참고하시면 추가된 조건을 확인해볼 수 있습니다.

## method
def sol(n,k):
    from collections import deque, defaultdict

    Min, Max = 0, 1e5
    will_visit = deque([n])
    visited = [-1]*(int(Max+1))
    visited[n]= 0
    answer = 0 #가능한 가짓수

    while will_visit:
        vx =  will_visit.popleft()
        if vx == k:
            answer += 1

        for nx in [vx+1, vx-1, vx*2]:
            # 새로 방문하게 될 nx가 이미 업데이트 된 상태에도 queue에 nx를 넣어주어야 하기 때문에 해당 조건이 사용됩니다.
            # 업데이트 된 값과 같아도 업데이트 가능합니다.
            if Min <= nx <= Max and (visited[nx] == visited[vx] + 1 or visited[nx] == -1):
                will_visit.append(nx)
                visited[nx] = visited[vx] + 1
    return visited[k],answer
            
## input
n, k = map(int, input().split())

## output
t,m = sol(n,k)
print(t)
print(m)

그런데 생각해보니, 어차피 목표지점까지의 최단시간을 찾아야하고, 최단시간을 가지는 다른 모든 경우의 수를 세야하기에 모든 노드를 한번씩 탐색해봐야 한다면, 그리고 노드별 최단시간을 업데이트하는 거라면 이 방식은 다익스트라를 활용할 때와 굉장히 비슷하더군요.

Dijkstra

모두 ∞으로 초기화된 노드에 최단시간으로 업데이트할 수 있는 노드가 나타난다면 업데이트 하는 방식은 동일. 하지만 굳이 가중치 작은 노드부터 업데이트해야 함을 고려하지 않아도 되며, 업데이트된 가중치와 동일한 경우도 queue에 넣어 방문해보도록 해서 가능한 경우의 수를 모두 count합니다.

## method
def sol(n,k):
    from collections import deque, defaultdict

    Min, Max = 0, 1e5
    will_visit = deque([n])
    visited = [float('inf')]*(int(Max+1))
    visited[n]= 0
    answer = 0 #가능한 가짓수

    while will_visit:
        vx =  will_visit.popleft()
        if vx == k:
            answer += 1

        for nx in [vx+1, vx-1, vx*2]:
            # 업데이트 필요한 경우를 가중치 같을 때(=)도 포함.
            if Min <= nx <= Max and visited[nx] >= visited[vx] + 1 :
                will_visit.append(nx)
                visited[nx] = visited[vx] + 1
    return visited[k],answer
            
## input
n, k = map(int, input().split())

## output
t,m = sol(n,k)
print(t)
print(m)

사실 바꾼건 몇개 없으나 ㅎㅎ.. 뭔가 기존에 작성해본 코드보다 직관적으로 작성할 수 있었던 코드라 같이 올려보았습니다.

아래 코드로 하니 약간 더 빨랐습니다