https://www.acmicpc.net/problem/11724

비슷한 문제: 프로그래머스 Level3 네트워크

풀이

1. 모든 노드를 bfs를 이용해 연결된 노드들을 탐색하고 visit 반환하고 카운트 증가
2. 1에서 탐색한 노드들은 탐색할 필요가 없으므로 이미 방문처리된 노드는 continue

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
nodes = {i:set() for i in range(n + 1)}
for _ in range(m):
    a, b = map(int, input().split())
    nodes[a].add(b)
    nodes[b].add(a)

def bfs(nodes, node):
    q = set()
    q.add(node)
    visit = set()
    while q:
        now = q.pop()
        if now not in visit:
            visit.add(now)
            q |= nodes[now]
    return visit
answer = 0
visit = set()
for i in range(1, n + 1):
    if i in visit:
        continue
    visit |= bfs(nodes, i)
    answer += 1

print(answer)

처음에는 list로 했는데 자꾸 시간초과나서 set으로 변경해 보았더니 통과됐다.