[PYTHON] 백준 11724 - 연결 요소의 개수

성능 요약

메모리: 179788 KB, 시간: 416 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

문제 설명

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

입력

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

출력

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

---

아이디어, 문제풀이

• 문제 자체는 기본 dfs든 bfs든 상관없이 그래프 탐색을 진행하며 총연결요소를 카운트 하면 되는 문제다. 즉, 연결된것들의 집합이 총 몇개인지를 알아내는 문제
• 모든 정점에서 연결요소가 새로운지를 판단하는데, 판단은 visit을 통해 가능하다.
• start의 visit이 0이라면 그래프탐색을 한뒤 1을 추가하고, 1이라면 이미 카운트된 연결요소 이기에 0을 추가한다.

---

TROUBLE SHOOTING

• 앞서서 여러 그래프 문제들을 풀어왔기에 난이도는 낮은편에 속한다. 이 문제를 풀기 전에 dfs를 풀다와서, 리마인드 할겸 queue를 활용한 bfs로 풀이했다.

• 이 문제를 풀었을때 빠르게 풀려 여유가 생겨서, 함수의 매개변수를 바꿔보며 python의 함수형에 대해 학습했다. 개념이 탄탄하다면 쉽게 이해하고 이미 적용하고 있었겠지만, 일단 이 코드상에서 보면,

  def bfs(start):
      
      que = deque()
      que.append(start)
  
      if visit[start] == 1:
          return 0
  
      else:
          while que:
              root = que.popleft()
              for node in graph[root]:
                  if visit[node] == 0:
                      visit[node] = 1
                      que.append(node)
  
                  if visit[node] == 1:
                      continue
          
          return 1

  bfs(start) 로만 매개변수를 지정해줘도 아무런 문제없이 작동한다. 이미 visit, graph가 전역변수로 지정되어있기 떄문에, 함수에서 따로 매개변수로 받지 않아도 그 값들을 받아올 수 있다.

  그럼에도 내가 bfs(graph, start, visit) 와 같게 작성하는 이유는, 함수 내부에서 활용하기 때문이다. 매개변수, 그리고 global 변수들을 자신이 어떻게 활용하느냐에 따라 크게 차이나기 때문에, 본인에게 맞는 방식을 찾는게 중요하다는 생각이 들었다. 결론이 밋밋하지만, 그래도 함수형에 대해서 한번 더 학습할 기회가 된것 같아 만족스러웠다.
  

---

코드

#https://www.acmicpc.net/problem/11724
#연결 요소의 개수
#11724

from collections import deque
import sys
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)
    # graph.sort(b)

# print(graph) 

visit = [0] * (n+1)

def bfs(graph, start, visit):
    
    que = deque()
    que.append(start)

    if visit[start] == 1:
        return 0

    else:
        while que:
            root = que.popleft()
            for node in graph[root]:
                if visit[node] == 0:
                    visit[node] = 1
                    que.append(node)

                if visit[node] == 1:
                    continue
        
        return 1
    
result = [0] * (n+1)
for i in range(1, n+1):
    result[i] = bfs(graph, i, visit)

answer = sum(result)

print(answer)