[Python] DFS/BFS - 11724.연결요소의 개수(실2)

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운점

 

---

1. 문제

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

11724번: 연결 요소의 개수

---

2. 핵심 아이디어

2-1) 연결요소의 정의

: 나누어진 각각의 그래프

 

조건

1) 연결 요소에 속한 모든 정점을 연결하는 경로 존재

2) 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안됨

=> 독립된 하나의 덩어리여야 함.

출처 : https://eunjk.tistory.com/22

예를 들어 위의 그래프는

2개의 연결요소로 구성된 하나의 그래프임

 

2-2) BFS와 DFS

DFS/BFS로 탐색이 끝난다는 말은

연결요소 하나의 탐색이 끝난다는 것과 같다.

 

예를 들어 위의그래프에서

1-2-3의 탐색이 끝나면 연결요소가 1개 탐색되며

4-5-6의 탐색이 끝나면 연결요소 1개가 마저 탐색이 끝난다.

 

즉, 탐색이 완료되는 시점에 하나씩 연결요소를 카운트해주면 된다.

---

3. 코드 구현

3-1) DFS 

def dfs(graph, v, visited):
  visited[v]=1

  for i in graph[v]:
    if visited[i]==0:
      dfs(graph, i, visited)

v,e = map(int, input().split())
graph= [[] for i in range(v+1)]
visited = [0]*(v+1)
result=0

for _ in range(e):
  a,b= map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

for i in range(1, v+1):
  if visited[i]==0:
     dfs(graph, i, visited)
     result+=1
print(result)

 

3-2) BFS 

from collections import deque

def bfs(graph, i, visited):
  q= deque([i])
  visited[i]=1

  while(q):
    now= q.popleft()
    for j in graph[now]:
      if visited[j]==0:
        q.append(j)
        visited[j]=1
    

v,e = map(int, input().split())
graph= [[] for i in range(v+1)]
visited = [0]*(v+1)
result=0

for _ in range(e):
  a,b= map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)

for i in range(1, v+1):
  if visited[i]==0:
     bfs(graph, i, visited)
     result+=1
print(result)

---

4. 배운점

- 연결요소의 정의를 잘 알고 있지 못하면 풀 수 없었던 문제

- DFS/BFS의 식을 정확히 구현할 줄 아는 상태에서 문제 해결 고리에 탐색이 필요하다는 것을 인지할 수 있는 능력이 부족하다는 생각이 들었다. 예를 들어 이번 연결요소 문제에서도 연결요소의 정의는 알고 있었지만 이것을 탐색과 연관지어 구현하겠다는 생각으로 이어지기 까지 시간이 걸렸다.

 

조금 더 유연하고 익숙해질 필요를 느낀다.