[구름톤 챌린지 WEEK 4 - 그래프 탐색] DAY 16.연합

이번 구름톤 WEEK4 주제는 그래프 탐색이다.

DFS, BFS 유형 문제가 너무 약해서 백준 기본 문제부터 공부를 시작하고 응용해보고 있다.

먼저 알고리즘 스터디에서 바이러스, DFS와 BFS 문제를 풀어보며 DFS, BFS로 순회하는 법을 배웠다.

이후에 구름톤 문제를 풀어보니 이에 + 서로 연결되어 있지 않은 연합, 컴포넌트 개수를 세는 문제들이 나왔다.

처음 접하는 유형이라 해설을 참고했다.

 

DAY 16. 연합

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [0] * (N + 1)
result = 0

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)

for i in range(1, N + 1):
    # 만약, 이미 어떤 연합에 속한 섬인 경우 건너뜀
    if visited[i]:
        continue

    # 처음 방문하는 섬인 경우 큐에 넣는다.
    q = deque([i])
    # 하나의 연합
    result += 1
    visited[i] = 1

    while q:
        now = q.popleft()
        # 현재 섬에서 도달 가능한 섬들 중에서
        for to in graph[now]:
            # 아직 방문하지 않았고, 그 섬에서 현재 섬으로 오는 간선이 있으면!
            if not visited[to] and now in graph[to]:
                # 큐에 추가, 방문 체크
                q.append(to)
                visited[to] = 1

print(result)

결과적으로 모든 섬을 방문해봐야 하기 때문에 BFS를 사용하는 편이 더 쉽다.

방문 체크를 하며 q에 섬을 넣어주고, 그 섬에 연결되어 있는(+방문하지 않은) 섬 중 반대로도 연결되는 양방향의 섬이 있으면 q에 넣어준다. 

 

이해가 잘 되지 않아 테케 2개를 손으로 세보니 이해가 되었다.