[TIL_Carrotww] 111 - 23/05/02

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 숨바꼭질2

처음 bfs로 풀었다.
bfs로 풀면 몇가지 제약이 있는 짜증났던 문제다
다익스트라로 풀면 특별한 조건 없이 그냥 풀리지만 처음 접근을 bfs로 하여서 끝까지 고집했지만 부러질뻔했다...ㅎ

• BFS 풀이

def solve():
    # bfs
    import sys
    from collections import deque
    N, K = map(int, sys.stdin.readline().split())
    visited = [-1] * 100001
    visited[N] = 0

    queue = deque()
    queue.append(N)
    while queue:
        cur_po = queue.popleft()
        if cur_po == K:
            print(visited[cur_po])
            break
        for i in range(3):
            if i == 0:
                n_po = cur_po * 2
            elif i == 1:
                n_po = cur_po - 1
            else:
                n_po = cur_po + 1

            if n_po < 0 or n_po >= 100001 or visited[n_po] != -1:
                continue
            if i == 0:
                if n_po != 0:
                    visited[n_po] = visited[cur_po]
                    queue.appendleft(n_po)
            else:
                visited[n_po] = visited[cur_po] + 1
                queue.append(n_po)

if __name__ == "__main__":
    solve()

문제가 어이 없는게 곱하기 부분이 먼저 들어가야해서 appendleft를 해주었는데 queue에 곱하기 부분을 먼저 넣어주지 않으면 안되는 케이스가 있다.
이것때문에 시간을 좀 쏟았다...ㅠ

• 다익스트라 풀이

def solve():
    # Dj
    import sys
    import heapq

    N, K = map(int, sys.stdin.readline().split())
    visited = [-1] * 100001
    heap = []
    heapq.heappush(heap, [0, N])

    while heap:
        cnt, cur_node = heapq.heappop(heap)
        if cur_node == K:
            print(cnt)
            break
        for i in range(3):
            if i == 0:
                n_cnt = cnt
                n_node = cur_node * 2
            elif i == 1:
                n_cnt = cnt + 1
                n_node = cur_node + 1
            else:
                n_cnt = cnt + 1
                n_node = cur_node - 1
            if n_node < 0 or n_node >= 100001 or visited[n_node] != -1:
                continue
            visited[n_node] = cnt
            heapq.heappush(heap, [n_cnt, n_node])

if __name__ == "__main__":
    solve()

훨씬 직관적이다.