알고리즘 풀이/백준

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

mhko411 2021. 2. 18. 23:03
728x90

문제

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

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다.

둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다.

 

출력

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


접근

2차원 리스트에 무방향 그래프를 표현하고 DFS를 탐색하여 연결 요소들을 찾는다. 이때 DFS가 실행된 수만큼 연결 요소의 수가 된다.

 

구현

정점과 간선을 입력받고 정점의 크기만큼 2차원 리스트를 생성한다.

그리고 방문표시를 위한 1차원 리스트도 생성한다. -> False로 초기화됨

N, M = map(int, input().split())
matrix = [[0 for _ in range(N)] for _ in range(N)]
visited = [False for _ in range(N)]

 

정점들의 정보를 입력받아 그래프에 나타낸다. 무방향 그래프이기 때문에 (u, v)와 (v, u)에 모두 1로 표시한다.

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    matrix[u][v] = matrix[v][u] = 1

 

visited의 해당 인덱스가 False이면 dfs를 실행한다. 그리고 방문하는 곳의 인덱스를 모두 True로 변경하여 중복으로 방문하지 못하도록 한다.

for idx in range(N):
    if not visited[idx]:
        answer += 1
        stack = []
        visited[idx] = True
        stack.append(idx)
        while stack:
            top = stack.pop()
            for j in range(N):
                if (not visited[j]) and matrix[top][j]:
                    visited[j] = True
                    stack.append(j)

전체 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [[0 for _ in range(N)] for _ in range(N)]
visited = [False for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    matrix[u][v] = matrix[v][u] = 1

answer = 0
for idx in range(N):
    if not visited[idx]:
        answer += 1
        stack = []
        visited[idx] = True
        stack.append(idx)
        while stack:
            top = stack.pop()
            for j in range(N):
                if (not visited[j]) and matrix[top][j]:
                    visited[j] = True
                    stack.append(j)

print(answer)

'알고리즘 풀이 > 백준' 카테고리의 다른 글

[백준 10250] ACM 호텔  (0) 2021.02.19
[백준 1085] 직사각형에서 탈출  (0) 2021.02.19
[백준 1003] 피보나치 함수  (0) 2021.02.18
[백준 1932] 정수 삼각형  (0) 2021.02.17
[백준 11726] 2xn 타일링  (0) 2021.02.17