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

Cat_Code 2022. 10. 31. 14:07

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주

www.acmicpc.net

[문제]

[코드]

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