김낭만

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

백준(BOJ) 1765 닭싸움 팀 정하기 파이썬(Python)

문제 링크

연결 요소(Connected Component)를 찾는 문제.
분리 집합(다른 말로 유니온 파인드)을 써도 되겠지만, BFS 한번, DFS 한번으로도 풀린다.
BFS를 통해 원수 그래프에서 거리가 2인 노드들의 친구 그래프에서 간선을 추가한다.
그 이후 친구 그래프의 연결 요소 개수를 세기 위해 DFS를 진행하면 된다.
인기 있는 문제가 아니라 그런지, 잘못된 이야기를 하는 블로거들이 많다.
단적인 예로, 친구의 원수의 원수는 친구가 아니라는 이야기가 많은데, 문제의 두 조건이 재귀적으로 적용되므로 이는 거짓이다.
친구의 원수의 원수는 친구의 친구이고, 따라서 친구이기 때문이다.
애시당초, 친구의 원수의 원수가 친구가 아니라면, 그 예시 자체가 이 문제의 기본 조건(친구끼리는 모두 팀을 맺어야 하고, 팀원들은 모두 친구여야 함)을 위반한다.
그런데도 문제를 맞혔다는 많은 블로거들이 이 부분을 헷갈려하고 있다.
심지어 어떤 블로거는 친구의 원수의 원수가 같은 팀이 될 수 없다고까지 하고 있다.
조금만 생각해봐도, 하다 못해 테스트 케이스만 넣어 봐도 이게 거짓임을 알 수 있는데, 도대체 문제를 어떻게 맞힌 걸까.
개인 공부용 블로그에만 의존하는 개발이 얼마나 위험한지를 보여주는 단적인 예시일 듯하다.

#!python

from sys import stdin, setrecursionlimit
from collections import deque
input = stdin.readline
setrecursionlimit(10 ** 6)

# 인접 리스트 형태로 그래프 2개(친구 그래프, 원수 그래프) 구현
n = int(input())
m = int(input())
graph = dict(zip(('F', 'E'), [[[] for _ in range(n + 1)] for _ in range(2)]))
visited = [False for _ in range(n + 1)]

for _ in range(m):
    f, p, q = input().split()
    p, q = map(int, (p, q))
    graph[f][p].append(q)
    graph[f][q].append(p)

# 원수 그래프에서 거리가 2인 노드를 찾기 위한 bfs
def bfs(node):
    q = deque()
    q.append((node, 0))
    while q:
        current, d = q.popleft()
        if visited[current]:
            continue
        visited[current] = True
        if d == 2:
            graph['F'][node].append(current)
        for next_node in graph['E'][current]:
            q.append((next_node, d + 1))

# 친구 그래프에서 연결 요소를 찾기 위한 dfs
def dfs(node):
    if visited[node]:
        return 0
    visited[node] = True
    for next_node in graph['F'][node]:
        dfs(next_node)

# 원수 그래프에서 각 노드에 대해 bfs를 수행한다
for node in range(1, n + 1):
    bfs(node)
    visited = [False for _ in range(n + 1)]

# 친구 그래프에서 각 노드에 대해 dfs를 수행한다
ans = 0
for node in range(1, n + 1):
    ans += dfs(node) is None

print(ans)

2024

맨 위로 이동 ↑

2023

세그먼트 트리

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

벨만-포드 알고리즘

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

다익스트라 알고리즘

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

맨 위로 이동 ↑