[구름톤 챌린지] 4주차 16일차 연합

문제

---

바다 위에 $N$개의 섬이 있다. 섬은 $1$번부터 $N$번까지 차례대로 번호가 붙어 있다. 서로 다른 두 섬 사이를 연결하는 $M$개의 다리도 있다. 모든 다리는 단방향으로만 이동 가능하고, 어떤 두 섬 사이를 잇는 다리는 정방향 하나, 역방향 하나씩 해서 최대 두 개이다.

어느 날, 섬들 사이에 분쟁이 일어났다. 모든 섬들은 세력을 키우기 위해 다른 섬과 연합을 결성하려고 한다. 임의의 두 섬 $a$와 $b$에 대해, $a$번 섬에서 $b$번 섬으로 직접 이동할 수 있는 다리와 $b$번 섬에서 $a$번 섬으로 직접 이동할 수 있는 다리가 있으면, 두 섬은 연합을 결성한다.
이때, $a$와 $b$가 연합을 결성하고 $b$와 $c$가 연합을 결성했다면 $a$와 $c$ 역시 위 조건을 만족하지 않더라도 같은 연합에 속해있는 것으로 본다.

다른 섬과 연합을 결성하지 않은 섬들도 각각 하나의 연합에 속해 있는 것으로 볼 때, $N$개의 섬 사이에 존재하는 연합의 개수를 구해보자.

입력

---

첫째 줄에 섬의 개수 $N$과 다리의 개수 $M$이 공백을 두고 주어진다.
다음 $M$개의 줄에는 $s_i, e_i$가 공백을 두고 주어진다. $s_i$번 섬에서 $e_i$번 섬으로 가는 다리가 있다는 의미이다.

 

 

• $2 \leq N \leq 2 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq s_i, e_i \leq N; s_i \neq e_i$
• 주어지는 모든 수는 정수이다.

출력

---

$N$개의 섬 사이에 존재하는 연합의 개수를 출력한다.

 

---

문제 접근 방식

---

연결 요소의 개수를 출력하는 문제로, DFS나 BFS와 같은 그래프 탐색을 해도 좋고 유니온-파인드와 같은 알고리즘을 써도 좋은 문제이다.

 

유의할 점은 문제에서 주어지는 간선이 단방향 간선이고, 실제로 연결되어 있는지의 여부는 양방향으로 갈 수 있는지를 따져주기 때문에, 간선을 입력받을 때 이를 걸러서 입력받아야 한다.

 

나의 경우 BFS로 접근해서 문제를 해결하였다.

 

---

정답 코드

---

# 연합
import sys
input = sys.stdin.readline
from collections import deque

N, M = map(int, input().rstrip().split())
graph = [[] for _ in range(N+1)]
visited = [0 for _ in range(N+1)]
edges = set()
for _ in range(M):
    u, v = map(int, input().rstrip().split())
    if (v, u) in edges:
        graph[u].append(v)
        graph[v].append(u)
    else:
        edges.add((u, v))

def BFS(node):
    queue = deque()
    queue.append(node)
    visited[node] = 1
    while queue:
        node = queue.popleft()
        for near_node in graph[node]:
            if visited[near_node] == 0:
                visited[near_node] = 1
                queue.append(near_node)
    return 1

total = 0
for node in range(1, N+1):
    if visited[node] == 0:
        total += BFS(node)
print(total)

 

---

특별히 배운 점

---

흔한 연결요소 문제 유형인데, 살짝 꼬아서 단방향/양방향으로 문제를 준 것이 조금 독특했다.

 

DFS나 유니온-파인드로도 풀어보면 더욱 좋을 문제인 것 같다.