[백준BOJ] 11724번 연결 요소의 개수.py

 

백준 저지에서 연결요소의 개수를 파이썬을 통해 풀어 보았다. 

 

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

11724번: 연결 요소의 개수

11724번 연결 요소의 개수.py

tomy9729/Algorithm

 

 

11724번 연결 요소의 개수

문제

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

설명

연결 요소의 개수를 구하라고 나와있는데 즉 그래프의 개수를 구하면 된다. 단 아무런 연결 없이 점 하나만 독립적으로 있더라도 그래프가 될 수 있다.

 

하나의 그래프를 찾기 위해 DFS를 사용했다. 모든 점에 대해서 반복문을 돌며 각 점에서 DFS를 시도한다. DFS를 통해 방문한 점은 체크해준다. 반복문을 돌며 접근한 점이 이미 방문한 점이라면 그 점은 이미 다른 그래프에 속한다는 의미이다. 한 번의 반복을 완전히 수행하면 하나의 그래프가 있는 것으로 간주한다. 

코드

#11724번 연결 요소의 개수
# import sys
# sys.setrecursionlimit(10**6)
# input = sys.stdin.readline
def DFS(graph, now, visited) :
  visited[now] = True # 방문
  for i in graph[now] :
    if visited[i] == False : # 방문하지 않았다면 
      DFS(graph,i,visited) # 탐색

if __name__ == "__main__":
  n, m = map(int,input().split())
  visited = [False]*(n+1)
  connect = [[] for i in range(n+1)]
  for i in range(m) : 
    point1, point2 = map(int,input().split())
    connect[point1].append(point2)
    connect[point2].append(point1)
  answer = 0
  for i in range(1,n+1) : 
    if visited[i] :
      continue
    DFS(connect,i,visited)
    answer += 1
  print(answer)