[BOJ] 연결 요소의 개수 파이썬 풀이

11724

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

풀이 방법

카테고리가 그래프 탐색인 만큼 BFS, DFS를 이용한 코드일것이라고 예상을 하고 문제풀이를 시작하였다.

첫번째로 그래프 탐색이 끝나면 자동으로 탐색이 종료된다는 특징을 이용하여, 탐색한 곳과, 탐색하지 않은 곳을 확인하는 코드로 작성하기로 했다.

 

그래프 탐색의 경우는 BFS와 DFS 모두 상관 없으므로 땡기는 DFS를 이용하기로 하였다.

방문한 곳과, 방문하지 않은 곳을 Bool 리스트로 표시하였고, While문을 순회하면서 방문하지 않은 노드들을 시작노드로 하여 코드를 작성하였다.

 

방문하지 않은 노드를 확인할 땐, index()를 사용하여 해당 인덱스 번호를 받아온 뒤, 1개를 더해주는 방식으로 인덱스를 맞춰주었다.

 

다만 아쉬운 점은 Python 으로 했을 땐 시간초과가 발생하였다는것과, 해당 이슈를 해결하지 못한 채 PyPy로 도망갔다는 것이며, sys의 시스템 input, output을 사용해서 다시한번 풀어봐야겠다.

풀이 코드

from collections import deque
def DFS(start, graph, visited):
    queue = [start]
    visited[start - 1] = True
    while queue:
        for i in graph[queue.pop()]:
            if not visited[i - 1]:
                visited[i - 1] = True
                queue.append(i)

    
if __name__ == "__main__":
    N, M = map(int, input().split())
    visited = [False for _ in range(N)]
    graph = {}
    for i in range (N):
        graph[i + 1] = set()

    for i in range(M):
        p, q = map(int, input().split())
        graph[p].add(q)
        graph[q].add(p)

    DFS(1, graph, visited)
    cnt = 1
    while True:
        try:
            DFS(visited.index(False) + 1, graph, visited)

            cnt += 1

        except Exception as e:
            break
    print (cnt)

 

결과