98. 백준 11724 번 Python 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

그래프 탐색 문제인 백준 11724 번 연결 요소의 개수 입니다.

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

11724번: 연결 요소의 개수

 

먼저 백준 11724 번 연결 요소의 개수 파이썬 정답 코드입니다. 설명은 아래에 있습니다.

import sys
input = sys.stdin.readline

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

#그래프 입력
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

#stack으로 DFS 구현, 재귀함수도 가능
def DFS(i):
    stack = [i]
    visited[i] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if not visited[y]:
                visited[y] = 1
                stack.append(y)

cnt = 0
for i in range(1, N+1):
    if not visited[i]:
        DFS(i)
        cnt += 1

print(cnt)

 

문제 요약

 

숫자를 노드, -를 간선으로 하는 그래프 1-5-4, 2-3 가 있습니다.

이 그래프는 1,4,5끼리. 2,3 끼리 연결 되어 있습니다.

이렇게 간선으로 연결된 노드들의 집합을 연결 요소라고 하고, 방금 예시를 든 그래프의 연결 요소의 개수는 2개입니다.

노드와 간선을 입력 받고 해당 그래프의 연결요소를 출력하는 문제입니다.

 

문제 접근

DFS, 혹은 BFS를 이용하여

1. 아직 한번도 방문하지 않고

2. 두 노드가 간선으로 연결된 경우에만 방문합니다.

위의 2가지 방법으로 모든 노드를 DFS, BFS를 통해 방문을 하게 되면

1. 한번도 방문하지 않은 연결 요소의 노드일 경우 나머지 모든 노드는 방문처리하게 됩니다.

2. 방문 했던 연결 요소의 노드일 경우 방문하지 못합니다.

 

따라서 연결 요소의 개수 만큼만 DFS, BFS가 동작하게 됩니다.

우리는 DFS, BFS 동작 횟수만 카운트 해주면 됩니다.

  

 

Python 코드 구현

 

노드와 간선의 개수, 그래프, 노드를 방문했는지 확인할 리스트 visitied 까지 선언하고 입력받습니다. 

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

#그래프 입력
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

 

연결된 요소들을 하나씩 방문하는 방법중 하나인 DFS를 구현했습니다. (stack으로 구현)

#stack으로 DFS 구현, 재귀함수도 가능
def DFS(i):
    stack = [i]
    visited[i] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if not visited[y]:
                visited[y] = 1
                stack.append(y)

 간선으로 연결된 노드 중 방문하지 않은 곳이 있다면 방문하는 방식입니다.

 

이제 모든 노드들을 탐색하면서 DFS가 동작한 횟수를 count 해주고 출력하면 됩니다.

cnt = 0
for i in range(1, N+1):
    if not visited[i]:
        DFS(i)
        cnt += 1

print(cnt)

 

 

백준 11724 번 연결 요소의 개수 Python 최종 코드입니다.

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for i in range(N + 1)]
visited = [False for _ in range(N + 1)]

#그래프 입력
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)

#stack으로 DFS 구현, 재귀함수도 가능
def DFS(i):
    stack = [i]
    visited[i] = True
    while stack:
        x = stack.pop()
        for y in graph[x]:
            if not visited[y]:
                visited[y] = 1
                stack.append(y)

cnt = 0
for i in range(1, N+1):
    if not visited[i]:
        DFS(i)
        cnt += 1

print(cnt)

 

백준 11724 번 연결 요소의 개수 자세한 설명 및 Python 코드였습니다.

감사합니다.