김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 13913 숨바꼭질 4 파이썬(Python)

문제 링크

BFS의 명가 숨바꼭질 시리즈의 중간보스격 문제.
여기에서는 경로를 출력해야 한다.
기본적으로 visited 배열에 이전 노드를 저장하든가 해서 역추적으로 풀면 되겠지만, 문제 평가에 역추적으로만 풀 수 있다는 얘기를 보고 조금 어거지이긴 하지만 새로운 풀이를 제시해보고자 한다.
기본적으로 방문한 경로를 모두 저장해서 넘겨주면 시간이든 메모리든 초과가 날 수밖에 없다.
이 풀이는 수빈이가 하는 세 가지 동작 중 두 가지가 단순한 증감 연산이라는 데에 착안하여, 경로를 압축하여 표현하는 풀이이다.
기본적으로 BFS를 하면서, 딱 두 가지 경우에만 경로 튜플을 갱신하고 그렇지 않은 경우 다음 노드에 그대로 넘겨준다.
첫 번째는 순간이동(*2)을 한 경우이고, 두 번째는 k에 도착한 경우이다.
이 경우, 그 직전의 노드(즉 현재 위치 말고 직전 위치)를 튜플에 저장한다.
그럼 튜플에는 순간이동 직전의 위치들과 k 바로 전 위치가 기록될 것이다.
이제 k에 도착하면 경로 튜플을 압축해제할 것인데, 인접한 원소 사이에는 증감 연산에 더해 마지막에 순간이동이 한번 적용될 것이다.
따라서, 다음 원소가 현재 원소보다 크다면 1씩 증가시키고 작다면 감소시키면서 다음 원소로 이동하고, 거기에 2를 곱하면 된다.
이걸 반복하면 도착 지점에 도착하는 것까지 전부 출력할 수 있다.
Pypy가 아닌 Python3 기준으로 200MB, 1.8초 정도의 시간에 풀 수 있다.
그리 효율적인 풀이는 아니지만 나름 참신하다고 생각한 풀이.

#!python

from collections import deque

n, k = map(int, input().split())
visited = [False for _ in range(200_000)] # 범위를 넘어가서 이동하는 게 더 빠를 수도 있으므로 넉넉하게 선언해줬다.
q = deque()
q.append((n, ())) # 시작 경로가 빈 튜플임에 주의

# BFS
while q:
    node, path = q.popleft()
    visited[node] = True
    # k에 도달한 경우
    if node == k:

        # 압축해제 과정
        ans = []
        prev = n
        for p in path:
            step = 1 if p > prev else -1
            for i in range(prev, p + step, step):
                ans.append(str(i))
            prev = 2 * p
        ans.append(str(k))

        정답 출력 후 break
        print(len(ans) - 1)
        print(' '.join(ans))
        break

    # 다음 노드들을 큐에 넣음
    for next_node in (node + 1, node - 1, node * 2):
        if not 0 <= next_node < 200_000 or visited[next_node]:
            continue

        # k에 도착하거나 순간이동을 한 경우에만 이전 노드를 추가하고 아니면 경로 튜플을 그대로 넘겨줌
        if next_node in (node * 2, k):
            q.append((next_node, path + (node, )))
        else:
            q.append((next_node, path))

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑