코딩테스트

[Python] 백준 11724 : 연결 요소의 개수

예린lynn 2025. 1. 20. 19:24
728x90

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

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 연결 요소의 개수를 출력한다.

📌 문제 탐색하기

문제부터 개념 이해까지 많은 공부와 복습이 필요했던 문제였다...

 

일단 문제에서 묻는 '연결 요소' 라는 개념에서부터 당황을 해버렸다. 그렇다면 연결 요소란 무엇일까?

연결 요소란?

1~6까지 모든 요소를 하나의 그래프라고 생각할 때, 아래 그림처럼 연결되지 않고 나누어져 있는 경우가 있다.

이때 나눠진 각각의 그래프를 연결 요소라고 한다. 아래 그림에서는 연결 요소가 2개인 것이다.

 

자 이제 뭘 구하라는 건지는 이해를 했다.

근데 이제 또 다시 든 궁금증, 그래서 그건 도대체 어떻게 구하는건데?

 

그렇게 또 찾아보다 보니 DFS/BFS 라는 개념을 접하게 됐다. 근데 분명 나 이거 학교 자료구조 시간에 배웠었는데...기억이 잘 안 나는 관계로 이참에 다시 정리해보려고 한다!

 

DFS

  • Defph First Search (깊이 우선 탐색)
  • 아래 그림과 같이 한 방향으로 최대한 깊이 내려간 뒤, 더이상 내려갈 곳이 없으면 옆으로 이동해서 탐색
  • 주로 모든 노드를 방문하고자 할 때 사용하는 방식
  • BFS보다 비교적 간단하지만, 검색 속도가 더 느리다

 

BFS 

  • Breadth First Search (너비 우선 탐색)
  • 시적점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문
  • 주로 최단 경로를 탐색할 때 사용

이 문제에서는 모든 경로를 확인해야 하기 때문에 dfs가 더 적합할 것 같다.

 

움...근데 역시 개념만으로는 코드를 어떻게 짜야할지 감이 너무나도 안 잡혀서...결국 이번만 해설 코드를 먼저 보고 공부하기로 결심했다...대신 이 기회에 dfs는 정복해야지!!!

📌 코드 설계하기

1. 입력값 가져오기

  • 파이썬에서는 재귀 깊이에 대한 호출 제한이 있기 때문에, 이 제한을 풀기 위해서는 다음과 같이 가져와야 한다.
sys.setrecursionlimit(10**6)
  • 첫 줄의 N,M 값 가져오기
N, M = map(int, sys.stdin.readline().split())

 

2. 인접 리스트 구현

  • 노드 번호를 인덱스로 사용하는 2차원 인접 리스트 생성
  • 1부터 N까지의 인덱스를 사용하기 위해 N+1로 범위 설정
  • 양방향 간선이므로 a->b, b->a 모두 값 할당

graph = [[] for _ in range(N+1)]
for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

//예시
graph = [
    [],        # 0번 노드 (사용하지 않음)
    [2, 3],    # 1번 노드와 연결된 노드: 2, 3
    [1, 5],    # 2번 노드와 연결된 노드: 1, 5
    [1, 4],    # 3번 노드와 연결된 노드: 1, 4
    [3],       # 4번 노드와 연결된 노드: 3
    [2]        # 5번 노드와 연결된 노드: 2
]

 

3. 탐색을 위한 배열 초기화

  • 기본값은 false로 설정하고, 탐색을 하면 true로 값 변경
visited = [False for _ in range(N+1)]

 

4. dfs 함수 구현 (제일 중요!!!)

  • node : 현재 방문 중인 노드의 번호
  • node와 연결된 모든 노드를 탐색하며, 방문 시 visited[node]=True
  • 현재 노드와 직접 연결된 노드들을 for문으로 순회
  • 방문한 노드의 재탐색을 방지하기 위해, if now visited[x] 만 탐색
  • 방문하지 않은 노드를 탐색하기 위해 dfs 함수를 재귀적으로 호출
def dfs(node):
    visited[node] = True
    for x in graph[node]:
        if not visited[x]:
            dfs(x)

 

5. 연결 요소 개수 구하기

  • 연결 요소 개수 ans=0으로 초기화
  • visited[i]가 false이면 ans값 증가
  • 연결 안 된 해당 노드 기준으로 새로운 연결된 그래프 dfs로 탐색
ans = 0
for i in range(1, N+1):
    if not visited[i]:
        ans += 1
        dfs(i)
print(ans)

📌 정답 코드

import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline

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)

visited = [False for _ in range(N+1)]    

def dfs(node) :
    visited[node]=True
    for x in graph[node]:
        if not visited[x]:
            dfs(x)

ans=0

for i in range(1,N+1):
    if not visited[i]:
        ans+=1
        dfs(i)

print(ans)

 

해설 : https://whydevsaysno.notion.site/9e619ebd5e784380a61b6196715edb52

728x90