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

12 Jan 2023 in Study on Algorithm

백준11724 연결 요소의 개수 링크

문제

예제 입력

---

코드

import sys
from collections import deque

n, m = map(int, input().split()) # 6 8
arr = [ [] for _ in range(n) ]
visit = [ False ] * n

for _ in range(m):
    u, v = map(int, sys.stdin.readline().split())
    arr[u - 1].append(v)
    arr[v - 1].append(u)

cnt = 0
def BFS(root) :
    global cnt
    flag = False
    dq = deque()
    dq.append(root)

    while dq :
        num = dq.popleft()
        if not visit[num - 1] :
            flag = True
            visit[num - 1] = True
            for val in arr[num - 1]:
                dq.append(val)
    if flag :
        cnt += 1

for i in range(n):
    BFS(i + 1)
print(cnt)

설명

파이썬을 통해서 사용자로부터 입력받아 자료형 list을 사용하여 BFS알고리즘으로 연결 요소의 개수를 구현했습니다.

---

정리

import sys
sys.setrecursionlimit(10000) # 파이썬은 재귀의 깊이를 제한 보통 10 ^ 5

def DFS(a):
    visit[a - 1] = True 
    for i in arr[a - 1]:
        if not visit[i - 1]:
            DFS(i)

cnt = 0
for w in range(n):
    if not visit[w]:
        DFS(w + 1)
        cnt += 1
print(cnt)

처음에는 자료형 list를 사용하여 DFS알고리즘으로도 구현이 가능하지만 재귀함수를 활용하기 때문에 비효율적입니다.

---

결과