[백준(python)] 11724 연결 요소의 개수

📌 난이도, 유형

난이도 : 실버2
유형 : 그래프 이론, 그래프 탐색, DFS, BFS
시간제한 : 3초
메모리제한 : 512MB

---

📌 문제설명

---

📌 입출력 예

---

📄 코드

BFS 풀이

from collections import deque
import sys

input = sys.stdin.readline

# N = 정점의 개수, M = 간선의 개수
N, M = map(int, input().split())
graph = [[0] * (N + 1) for _ in range(N + 1)]
visited = [False] * (N + 1)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

def bfs():
    global result
    while queue:
        cur = queue.popleft()
        for i in range(N + 1):
            if not visited[i] and graph[cur][i]:
                visited[i] = True
                queue.append(i)
    result += 1

result = 0
queue = deque([])
for i in range(1, N + 1):
    if visited[i] == False:
        queue.append(i)
        visited[i] = True
        bfs()
print(result)

DFS 풀이

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

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

def dfs(idx):
    global result
    visited[idx] = True
    for i in range(N + 1):
        if not visited[i] and graph[idx][i]:
            dfs(i)
            
for _ in range(M):
    a,b = map(int, input().split())
    graph[a][b] = True
    graph[b][a] = True

for i in range(1, N + 1):
    if visited[i] == False:
        dfs(i)
        result += 1
print(result)

---

📝 해설

무방향 그래프, visited 리스트를 사용해서 들린 정점에 표시를 해주고 탐색이 끝나고 result에 +1 을 해주었다.