[백준/파이썬] 11724번

📍백준 11724번 문제

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

코드

import sys
from collections import deque
input = sys.stdin.readline
m, n = map(int, input().split())


def bfs(start_node):
    que = deque([start_node])
    visited[start_node] = True
    while que:
        node = que.popleft()
        for i in graph[node]:
            if not visited[i]:
                visited[i] = True
                que.append(i)


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

visited = [False] * (m+1)

count = 0

for i in range(1, m+1):
    if not visited[i]:
        if not graph[i]:
            count += 1
            visited[i] = True
        else:
            bfs(i)
            count += 1

print(count)

풀이

bfs를 이용해서 풀었다.
먼저 무방향 그래프이므로 2차원 배열을 통해 값을 넣어준다.
방문을 하지않았고, 그래프에 값이 존재하지 않는다면 count에 1을 더해주었다. 방문을 하지않고 그래프에 값이 존재한다면 bfs를 이용해 연결된 노드를 방문하였고 모두 true로 바꿔주면 된다.