BOJ-백준11724번 연결 요소의 개수

BOJ-백준11724번 연결 요소의 개수 Python 문제 풀이 입니다.

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

11724번: 연결 요소의 개수

문제

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

 

✅ Python 정답 코드 입니다.

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

def dfs(root):
  visited[root-1] = True
  for v in dict_graph[root]:
    if not visited[v-1]:
      dfs(v)
  return 

n,m = map(int,input().split())
dict_graph={}
visited = [False]*n
for i in range(1,n+1):
  dict_graph[i]=[]
for _ in range(m):
  u,v = map(int, input().split())
  dict_graph[u].append(v)
  dict_graph[v].append(u)
connection = 0
for root in dict_graph:
  if not visited[root-1]:
    dfs(root)
    connection +=1
print(connection)

📌 해설

DFS를 수행해서 graph를 탐색합니다. dictionary에 양 방향 그래프 정보를 저장하고 방문한 노드는 방문표시를 합니다. DFS가 종료되면 연결요소의 수를 증가시킵니다.

 

🚩 주의

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

재귀호출의 깊이 제한을 바꾸고, sys.stdin.readline을 통해 효율적으로 input을 받을 수 있도록 합니다. 

 

def dfs(root):
  visited[root-1] = True
  for v in dict_graph[root]:
    if not visited[v-1]:
      dfs(v)
  return

1. dfs 함수를 구현합니다. 

1-1. root는 정점(Vertex)를 의미합니다. 

1-2. visited에 현재 정점을 방문표시(True)합니다.

1-3. 현재 정점과 연결된 정점들(dict_graph[root])을 조회하는 for 문을 작성합니다.

1-4. 연결된 정점(v)이 이미 방문한 곳인지 확인합니다.

1-5. 방문하지 않았으면(not visited[v-1]) dfs 탐색을 재귀호출 합니다.

 

n,m = map(int,input().split())
dict_graph={}
visited = [False]*n
for i in range(1,n+1):
  dict_graph[i]=[]
for _ in range(m):
  u,v = map(int, input().split())
  dict_graph[u].append(v)
  dict_graph[v].append(u)

2. n(정점의 개수), m(간선의 개수) 를 입력받고 정점의 개수만큼 visited 리스트를 선언합니다. 방문을 했는지 안 했는지 확인 하므로 bool type이 됩니다. 

dict_graph는 양방향 그래프기 때문에 u~v, v~u를 딕셔너리 그래프에 저장합니다. 

 

connection = 0
for root in dict_graph:
  if not visited[root-1]:
    dfs(root)
    connection +=1
print(connection)

3. dict_graph를 모두 조회하는 for 문을 작성합니다.

3-1. 방문하지 않은 정점인지 확인하고 방문하지 않았으면 dfs 탐색을 호출합니다. 

3-2. dfs 탐색이 끝나면 connection을 1 증가시킵니다. 

 

 

:: 

 

 

DFS 탐색은 계속 반복해서 풀면서 감을 익혀야 겠어요!!!! 

혼자 문제 풀 수 있을 때 까지 화이팅!!