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

📌 백준 11724 - 연결 요소의 개수

문제 설명

---

💡 나의 풀이

이번 문제는 BFS와 DFS 모두 이용해서 풀었는데 시간 차이가 많이 나지 않았다.(근소하게 DFS가 48m/s정도 빨랐다.) 무방향 그래프가 없을 때는 입력값을 반대로 바꿔서 넣어줘도 된다.

728x90

예제 입력1을 그림으로 표현하면 다음과 같다. 문제를 쉽게 그림으로 표현했다. graph의 index가 노드이다. DFS로 풀 때는 최대 재귀 값을 더 열어줘야 풀린다.

 

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

def dfs(graph, v, visited):    # dfs implementation
    visited[v] = True

    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
visited = [False] * (N + 1)

for i in range(M):
    node1, node2 = map(int, input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

cnt = 0
for i in range(1, N+1):    # check each node
    if not visited[i]:
        dfs(graph, i, visited)
        cnt += 1
print(cnt)