김낭만

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

백준(BOJ) 12851 숨바꼭질 2 파이썬(Python)

문제 링크

BFS를 통해 최단 거리를 찾는 문제.
숨바꼭질 1과 다르게 방법의 수까지 출력해야 한다.
가능한 모든 방법을 전부 찾기 위해서, 답을 찾더라도 break를 통해 종료하지 않고 continue로 가능한 범위를 계속 순회한다.
또한, visited 리스트가 거리를 저장하게 만들어서 최단거리로 간 거리를 다시 탐색하지 않도록 했다.
n == k인 경우를 따로 예외처리를 했는데, 검사 순서를 조금 바꾸면 예외처리하지 않고도 처리할 수 있을 것 같다.
처음에 이 예외처리를 바보같이 0\n0을 출력하도록 하는 바람에 오답을 냈다.

from collections import deque
INF = float('inf')

n, k = map(int, input().split())

visited = [INF] * 100001
q = deque()
q.append((n, 0))
visited[n] = 0
ans = 0
ways = 1

# n == k인 경우의 예외처리
if n == k:
    print('0\n1')

else:
    while q:
        num, dist = q.popleft()
        # 덧셈, 뺄셈, 곱셈
        for func in (lambda x: x+1, lambda x: x-1, lambda x: x*2):
            new = func(num)
            # 동생 위치에 도달한 경우
            if new == k:
                # 처음 도달했다면 정답으로 저장
                if not ans:
                    ans = dist + 1
                # 처음이 아니라면 최단거리인지 확인한 후 방법의 수를 하나 늘림
                elif ans == dist + 1:
                    ways += 1
                continue
            elif 0 <= new <= 100000 and dist + 1 <= visited[new]:
                visited[new] = dist + 1
                q.append((new, dist + 1))
    
    print(ans, ways, sep = '\n')

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑