[BOJ][python] 연결 요소의 개수

그래프 객체 생성 및 입력 메소드에 따른 시간초과 해결  

 

문제

---

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

 

입력

---

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

 

나의 풀이

---

처음 문제를 풀었을 때는 visited를 숫자로 놓고 count로 flag를 체크 했었는데 boolean으로 체크하는 것이 속도도 빠르고 안정적이라는 것을 발견해서 visited 리스트를 수정했습니다.

그럼에도 불구하고 시간초과가 발생했는데, sys에서 제공하는 readline 메소드를 사용하니 시간초과를 해결할 수 있었습니다.

이 메소드를 사용하지 않고 해결하는 방법을 좀 더 연구해야 할 것 같습니다.

import sys
read = lambda : sys.stdin.readline().strip()

class Graph:
    
    def __init__(self, V) :
        self.V = V
        self.adj = [[] for i in range(V)]
    
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)
    
    def BFS(self, v, visited):
        visited[v] = True
        queue = []
        queue.append(v)
        while len(queue) > 0:
            d = queue.pop()
            for i in self.adj[d]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True
        return
        
    def countConnectedComponents(self):
        visited = []
        count = 0
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                self.BFS(v, visited)
                count = count + 1
        return count
                
        
    
if __name__ == "__main__":
    n, m = map(int,read().split())
    c = [list(map(int,read().split())) for _ in range(m)]
    g = Graph(n)
    for v, w in c:
        g.addEdge(v-1, w-1)
    answer = g.countConnectedComponents()
    print(answer)