[BOJ]11724 - 연결 요소의 개수 (Python)

문제

https://www.acmicpc.net/problem/11724

코드

import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10000)

def dfs(v):
    visited[v] = 1
    for i in range(1, N+1):
        # 연결되어 있고 visited 아니면 다시 탐색
        if s[v][i] == 1 and visited[i] == 0:
            dfs(i)

N, M = map(int, input().split())
s = [[0] * (N+1) for i in range(N+1)]
visited = [0 for i in range(N+1)]
count = 0

for i in range(M):
    a, b = map(int, input().split())
    # a와 b 연결됨
    s[a][b] = 1
    s[b][a] = 1

for i in range(1, N+1):
    if visited[i] == 0:
        dfs(i)
        # 연결되어 있지 않고 visited 이면 하나의 connected component 생긴 것
        count += 1

print(count)

풀이

DFS/BFS를 사용해서 풀면 되는 문제이다

개념을 이해했다고 생각했는데 막상 문제를 풀어보려고 하니 구현이 어려워서 답을 보고 이해하는 방법을 선택했다

 

• sys.setrecursionlimit(10000) :  파이썬의 최대 재귀 횟수는 1000인데 이를 넘으면 오류가 나기 때문에 새로운 최대 재귀 횟수를 설정
• 입력받은 2개의 node를 연결시키고 연결된 node들 사이를 돌면서 탐색. 더이상 방문할 곳이 없으면 하나의 connected component가 생긴 것