김낭만

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

백준(BOJ) 1304 지역 파이썬(Python)

문제 링크

입력이 작아서 적당히 풀어도 풀리는 간단한 그래프 문제.
작은 번호 노드에서 큰 번호 노드로는 항상 길이 있으므로 큰 번호 노드에서 작은 번호 노드로 가는 엣지만 의미를 갖는다.
이를 기반으로 DFS를 해서 일종의 유사 연결 요소(정확히는 지역 후보로, 여기서는 무조건 같은 지역이어야 하는 노드들의 집합)를 구할 수 있다.
그 이후 해당 지역 후보들을 합쳐서 하나의 지역을 만드는데, 지역의 노드 개수는 모두 같아야 하므로 그 경우를 확인하면 된다.
이때, 지역들은 모두 연속된 번호여야 하는데, 그렇지 않으면 서로 다른 두 지역이 지역의 조건을 만족할 수 없기 때문이다.
사실, 이거보다 간단한 풀이가 있는데, 나는 어쩌다 보니 이렇게 빙 돌아서 풀게 됐다.
그래도 입력이 작고 시간 제한도 널널해서 풀이 방법이 크게 상관이 없는 문제.

#!python

from sys import stdin
input = stdin.readline

# dfs 함수, dfs의 결과로 방문한 가장 작은 노드 번호를 반환한다
def dfs(node):
    visited[node] = True
    ret = node
    for next_node in graph[node]:
        if visited[next_node]:
            continue
        ret = min(ret, dfs(next_node))
    return ret

n, m = map(int, input().split())
graph = [[] for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]
# arr은 지역 후보(같은 지역이어야 하는 노드들의 집합)들의 크기를 저장한다
arr = []

# 간선을 저장하는데, s가 e보다 작은 경우는 고속 도로를 통해 이미 경로가 마련되어 있으므로 무시해도 된다
for _ in range(m):
    s, e = map(int, input().split())
    if s <= e:
        continue
    graph[s].append(e)

# 각 노드를 높은 수부터 순회하며 지역 후보들의 크기를 저장한다
j = n
for i in range(n, 0, -1):
    if visited[i]: 
        continue
    if i > j:
        k = dfs(i)
        if k > j:
            continue
        arr[-1] += j - k
        j = k
        continue
    j = dfs(i)
    arr.append(i - j + 1)

# 가장 큰 지역 후보의 크기부터 노드 개수의 절반까지
for s in range(max(arr), n // 2 + 1):
    temp = 0
    # 그리디하게 순회하면서 같은 수의 지역으로 나눠지는지 확인한다
    for e in arr:
        temp += e
        if temp == s:
            temp = 0
        elif temp > s:
            break
    # 같은 개수의 지역으로 나눠지면 그 값을 출력한다
    else:
        if not temp:
            print(n // s)
            break
# 나눠지는 경우가 없으면 모든 노드가 하나의 지역인 경우이므로 1을 출력한다
else:
    print(1)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑