김낭만

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

백준(BOJ) 1613 역사 파이썬(Python)

문제 링크

간단한 그래프 문제.
유향 그래프(Directed Graph)의 방문 가능 여부를 확인하는 문제이다.
위상 정렬(Topology Sort)을 이용해 노드 간 순서를 파악해서 풀 수 있다.
또는 플로이드-워셜(Floyed-Warshall) 알고리즘을 통해 모든 노드 간의 최단거리를 구해도 된다.
또는 단순 그래프 탐색을 각 노드마다 한 번씩 해도 된다.
위상 정렬은 구현이 귀찮고, 플로이드 워셜은 \(O(V^3)\)이고, 그래프 탐색(즉, BFS나 DFS)은 노드 수만큼 반복해도 \(O(V^2 + VE)\)이므로 그래프 탐색으로 풀었다.
정확히는 BFS로 풀었는데, 단순히 collections.deque()를 사용하거나 큐를 직접 구현해야 하는 DFS보다 그냥 스택을 쓰는 BFS가 편해서 그런 것 뿐이다.
아무튼, 각 노드에 대해서 BFS를 수행해서 방문 가능한 지점들을 모두 확인해 두면 간단하게 문제를 풀 수 있다.

#!python

from sys import stdin
input = stdin.readline

# reach[i][j]는 i번 노드에서 j번 노드로의 경로 존재 유무
n, k = map(int, input().split())
graph = [[] for _ in range(n + 1)]
reach = [[False for _ in range(n + 1)] for _ in range(n + 1)]
stack = []

# 인접 리스트 그래프
for _ in range(k):
    curr, succ = map(int, input().split())
    graph[curr].append(succ)

# BFS를 n번 반복
# visited 리스트 대신에 reach[node]를 사용했다
for node in range(1, n + 1):
    stack.append(node)
    while stack:
        curr = stack.pop()
        for succ in graph[curr]:
            if reach[node][succ]:
                continue
            reach[node][succ] = True
            stack.append(succ)

for _ in range(int(input())):
    a, b = map(int, input().split())
    if reach[a][b]:
        print(-1)
    elif reach[b][a]:
        print(1)
    else:
        print(0)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑