BOJ 11724 연결 요소의 개수 풀이

[allzeroyou]

문제 분석

첫 번째 단계(문제 요약 및 조건 파악)

방향 없는 그래프가 주어졌을때, 연결 요소의 개수를 구하기.

입력

• 정점의 개수 N, 간선의 개수 M(1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2)
• M개의 줄에 간선의 양 끝점 u, v가 주어짐(1 ≤ u, v ≤ N, u ≠ v)
• 같은 간선은 한 번만 주어짐.

출력

• 연결 요소의 개수 출력

두 번째 단계 (문제 핵심 파악)

방향 없는 그래프는 즉, 순환성 그래프이다.

연결 요소는 그래프 별로 덩어리로 되어있기 때문에, 모든 노드를 방문해주어야 함(이때 탐색 순서는 상관이 없음.)

그래프 표현시→ 인접 행렬 or 인접 리스트(인접 리스트(희소), 인접 행렬(밀집))

이때 최대 간선의 개수가 N×(N-1)/2인데, 이 값은 큰 값(밀집)인가 작은 값(희소)인가?

u ≠ v이므로 nC2임. nC2는 수식으로 N×(N-1)/2이다. 이는 N이 1000일때 큰 값이므로, 인접 행렬을 사용한다.

코드 작성

최종 코드

import sys

input = sys.stdin.readline # n이 최댓값일 경우에 대비해 빠른 입력
# RecursionError 방지용
sys.setrecursionlimit(10 ** 8)

def dfs(now): # 현재 노드
 for nxt in range(n): # 다음 열
 if graph[now][nxt] and not chk[nxt]: # 그래프로 갈 수 있고, 방문을 안 했을 경우
 chk[nxt] = True # 방문 체크
 dfs(nxt) # dfs 실행

n, m = map(int, input().split())
# 인접 행렬(N X N 2차원 리스트)
graph = [[0] * n for _ in range(n)] # 0-based
# 간선
for _ in range(m):
 u, v = map(lambda x: x - 1, map(int, input().split())) # 1-based to 0-based
 graph[u][v] = 1 # 간선으로 연결된 노드임.
 graph[v][u] = 1 # 무방향==양방향

# for i, row in enumerate(graph):
# print(f'{i}: {row}')

ans = 0
# 방문 체크용
chk = [False] * n

for i in range(n):
 if not chk[i]:
 chk[i] = True
 ans += 1
 dfs(i) # dfs
print(ans)

아래 코드로 제출 하면 RecursionError 가 발생한다.

파이썬 기본 재귀 depth를 초과(10*3)했기 때문이다.

따라서, 최종 코드인 위에는 depth를 늘려주었다.

RecursionError 발생 코드

import sys

input = sys.stdin.readline # n이 최댓값일 경우에 대비해 빠른 입력

def dfs(now): # 현재 노드
 for nxt in range(n): # 다음 열
 if graph[now][nxt] and not chk[nxt]: # 그래프로 갈 수 있고, 방문을 안 했을 경우
 chk[nxt] = True # 방문 체크
 dfs(nxt) # dfs 실행

n, m = map(int, input().split())
# 인접 행렬(N X N 2차원 리스트)
graph = [[0] * n for _ in range(n)] # 0-based
# 간선
for _ in range(m):
 u, v = map(lambda x: x - 1, map(int, input().split())) # 1-based to 0-based
 graph[u][v] = 1 # 간선으로 연결된 노드임.
 graph[v][u] = 1 # 무방향==양방향

# for i, row in enumerate(graph):
# print(f'{i}: {row}')

ans = 0
# 방문 체크용
chk = [False] * n

for i in range(n):
 if not chk[i]:
 chk[i] = True
 ans += 1
 dfs(i) # dfs
print(ans)

느낀점

그래프 문제는 dfs, bfs로 접근해야 함은 알겠는데 적절하게 인접리스트, 인접행렬을 선택해 푸는 것은 어려운 것 같다.