[백준] 11724번 연결 요소의 개수 / 파이썬(python)

# 문제 링크

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

11724번: 연결 요소의 개수

# Soultion

처음에 dfs를 이용하여 문제를 풀었더니 recursion 에러가 발생하여 재귀깊이를 설정해주었다.

그래도 동일하게 문제가 발생하여 bfs로 풀었더니 동일한 에러가 발생하였다.

알고보니 input()을 받는과정에서 시간초과가 발생하였다.

 

import sys
from collections import deque
n,m = map(int,input().split())
graph = [[]*n for _ in range(n+1)]
for _ in range(m):
    u,v = map(int,sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)
 
visited = [0]*(n+1) # 방문체크
 
def bfs(n):
    queue = deque([n])
    while(queue):
        n = queue.popleft()
        for node in graph[n]:
            if visited[node]==0:
                queue.append(node)
                visited[node]=1
               
cnt = 0
for i in range(1,n+1):
    if visited[i]==0:
        bfs(i)
        cnt+=1
print(cnt)

 

 

6. input()으로 입력값을 받을때, readline()함수로 입력받음

7~8. 각 노드들의 연결정보를 graph라는 리스트에 저장

10. 노드방문 체크를 위한 1차원 리스트 (0으로 초기화)

12. bfs 동작

22. 1부터 n까지의 노드들을 확인

23. 방문하지 않은 노드가있다면 bfs를 이용하여 방문