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

11724번: 연결 요소의 개수

[문제]

---

[코드]

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

def dfs(start, depth):

    visited[start]  = True

    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

count = 0
visited = [False] * (n+1)

for i in range(1, n+1):
    if not visited[i]:
        if not graph[i]:
            count += 1
            visited[i] = True
        else:
            dfs(i, 0)
            count += 1

print(count)

---

[해설]

DFS - 깊이 우선 탐색을 통해서 문제를 풀이하는 방식이다

우선 아래의 부분은 

sys.setrecursionlimit(100000)

지정하지 않으면 백준에서 에러가 뜨기 때문에 깊이의 범위를 설정해준다

 

핵심 코드는 아래의 dfs 코드와

def dfs(start, depth):

    visited[start]  = True

    for i in graph[start]:
        if not visited[i]:
            dfs(i, depth + 1)

for 문을 사용해서 dfs를 돌려 이미 방문했던 곳이면 넘어가고 

아무것도 연결되어 있지 않는 곳이라면 count에 1을 올려주고 방문처리한다

그리고 나머지의 dfs 함수를 돌려서 방문처리한고 count에 1을 올려준다

for i in range(1, n+1):
    if not visited[i]:
        if not graph[i]:
            count += 1
            visited[i] = True
        else:
            dfs(i, 0)
            count += 1