백준 - 11724. 연결요소의개수 파이썬

 

11724번: 연결 요소의 개수

1. SOLUTION

dfs, bfs 모두 사용해서 풀 수 있어서 그래프 연습하기 딱 좋은 문제인듯

나는 dfs를 재귀로 구현했다. 추후에 bfs로도 풀어보자

from collections import defaultdict

graph = defaultdict(list)
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

defaultdict를 사용해 인접리스트 형태로 그래프를 입력받으면 편하다.

모든 키에 대해서 value가 없는 경우 자동으로 인자로 받은 자료형(여기서는 list)을 기본 값으로 설정해 준다.

collections 모듈의 defaultdict 클래스를 import 해서 사용할 수 있다.

def dfs(s):
    # 재귀로 dfs 구현
    if visited[s]:				
        return
    visited[s] = True           # 시작지점 방문처리
    for node in graph[s]:       # 시작지점과 연결된 노드 중
        if not visited[node]:   # 방문하지 않은 노드에서 dfs 수행
            dfs(node)
            
 visited = [False] * (N + 1)

스택 사용해서 dfs 구현하는 건 뭔가 손에 안익어서 재귀를 사용했다.

시작지점(s)가 이미 방문처리 되어 있을 경우 return해주는 것으로 중단조건을 설정해 주었고,

시작지점을 방문처리 해 주고 이 지점과 연결된 노드 중 방문하지 않은 노드에서 dfs를 재귀적으로 수행시켜줬다.

 

노드 번호가 1번부터 시작하기 때문에 visited의 길이를 N + 1로 설정 해 주었다.

cnt = 0

# 1 ~ N번 노드 돌면서 방문한적 없는 노드에서 dfs 수행
for i in range(1, N + 1):
    if not visited[i]:
        dfs(i)
        cnt += 1

서로 연결되어 있는 노드 덩어리(?)가 몇 개인지 구하는 문제이므로 1번부터 N번 노드까지를 반복문으로 돌면서,

방문한 적 없는 노드에서 dfs를 수행해주고 그 때마다 결과값에 1을 더해주면 된다.

그대로 제출하면 Recursion에러 뜸ㅎㅎ....

파이썬에서 제한해둔 재귀 깊이 = 1000이라 sys.setrecursionlimit로 깊이를 재설정 해줘야 한다.

dfs로 풀 때 꼭 잊지말자...ㅠ 

2. CODE

import sys
from collections import defaultdict
sys.setrecursionlimit(10000)

def dfs(s):
    # 재귀로 dfs 구현
    if visited[s]:
        return
    visited[s] = True           # 시작지점 방문처리
    for node in graph[s]:       # 시작지점과 연결된 노드 중
        if not visited[node]:   # 방문하지 않은 노드에서 dfs 수행
            dfs(node)


N, M = map(int, sys.stdin.readline().split())
graph = defaultdict(list)
visited = [False] * (N + 1)
cnt = 0
# 인접리스트 생성
for _ in range(M):
    u, v = map(int, sys.stdin.readline().split())
    graph[u].append(v)
    graph[v].append(u)

# 1 ~ N번 노드 돌면서 방문한적 없는 노드에서 dfs 수행
for i in range(1, N + 1):
    if not visited[i]:
        dfs(i)
        cnt += 1

print(cnt)