[🥲 백준] 11724번 연결요소의 개수 - BFS/DFS

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

11724번: 연결 요소의 개수

 

🍪 내 풀이 

# 시간 초과
import sys
a,b = map(int,sys.stdin.readline().split())
connect_graph = {i:[] for i in range(1, a+1)} # 연결관계 그래프

# 그래프에 값을 넣어줌
for _ in range(b):
    c,d = map(int,sys.stdin.readline().split())
    connect_graph[c].append(d)
    connect_graph[d].append(c)

stack = []
visited = []
all_numbers = [i for i in range(1, a+1)]
count = 0

# all_numbers에 값이 있는 경우
while all_numbers:
    stack.append(all_numbers[0])
    count += 1 # 새로 넣어주는 경우는 연결이 끊겼다는 뜻
    while stack: #
        component = stack.pop(0)
        if component not in visited:
            all_numbers.remove(component)
            visited.append(component)
            stack.extend(connect_graph[component])

print(count)

시간초과 ㅠㅠ 답이 안나와서 다른 사람들 풀이를 참고했는데

대다수가 재귀로 풀었다....

 

🍪 다른사람 풀이

import sys
sys.setrecursionlimit(10000) # 최대 재귀한도 설정

def dfs(i, G, V, N):
    V[i] = True # 방문했다고 변경
    for j in range(1, N+1):
        if V[j] == True or G[i][j] == 0: # 방문했거나 연결관계가 없는 경우
            continue # dfs 실행 x
        dfs(j, G, V, N)


def _11724():
    N = 1001
    graph = [[0] * N for i in range(N)] # 그래프 생성
    visited = [0] * N

    U, V = map(int,input().split(' '))
    for i in range(V):
        u, v = map(int, sys.stdin.readline().split())

        graph[u][v] = 1 # 둘이 연결관계가 있으면 1 아니면 0
        graph[v][u] = 1

    count = 0
    for i in range (1, U+1): # 전체 숫자에서
        if visited[i] == 0: # 방문하지 않았을 경우
            dfs(i, graph, visited, U) # 방문했다고 변경하는 함수
            count += 1

    print(count)
    
_11724()