[BOJ] 11724 / 연결 요소의 개수 / Python 파이썬

[BOJ] 11724 / 연결 요소의 개수 / Python 파이썬

[BOJ] 11724 / 연결 요소의 개수 / Python 파이썬

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

11724번: 연결 요소의 개수

 

풀이

그래프를 구성하는 노드와 엣지를 입력받아, 연결되어 있는 그래프의 수를 구하는 문제이다.

 

BFS 로 그래프의 구성을 확인하였고, BFS 는 queue 로 구현하였다.

 

import sys

def countGraph(N, graph):
    if N == 1:
        return 1
    visited = []
    res = 0
    for n in range(1, N+1):
        if n not in visited:
            res += 1
            queue = [n]

            while queue:
                f = queue.pop(0)
                visited.append(f)
                for t in range(1, N+1):
                    if graph[f][t] and t not in visited:
                        queue.append(t)
                        visited.append(t)
    return res

N, M = map(int, sys.stdin.readline().split())

graph = [[0 for _ in range(N+1)] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u][v] = 1
    graph[v][u] = 1

print(countGraph(N, graph))