[백준/Python] 11724 연결 요소의 개수

 

 

• dfs 로 구현하려 했으나 파이썬 재귀제한에 걸려 재귀 제한을 넓혀주는 sys.setrecursionlimit(10000) 코드를 추가 했지만, 시간초과가 떠서 bfs로 구현하였다.
• bfs도 시간초과가 떠서 input 대신 sys.stdin.readline를 이용하였다.

 

from collections import deque
import sys
input = sys.stdin.readline 

V, E = map(int,input().split())
arr = [[0] * V for _ in range(V)]
used = [0]*V
cnt = 0

for i in range(E):
    y,x = map(int,input().split())

    arr[y-1][x-1] = 1
    arr[x-1][y-1] = 1

def bfs(now): # 연결 요소들을 bfs를 통해 다시 방문하지 않도록 해줌
    q = deque()
    q.append(now)

    while q:
        node = q.popleft()
        for i in range(V):
            if arr[node][i] == 1 and used[i] == 0:
                used[i] = 1
                q.append(i)

for j in range(V):
    flag = 0
    for i in range(V):
        if arr[j][i] == 1:
            flag = 1
            if used[j] == 0:
                used[j] = 1
                cnt += 1 # bfs가 실행될때마다 cnt + 1
                bfs(j)
    if flag == 0: # 연결 요소가 없는 정점이 없다면 카운트 추가
        cnt += 1

print(cnt)