[Python] 백준 풀기 11724 - 연결 요소의 개수

파이썬 백준 11724번

실버2

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

11724번: 연결 요소의 개수

 

 

 

 

 

문제 보기

분류: 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

 

 

 

 

 

문제 풀기

"연결 요소의 개수" 라 하면 아무리 생각해도 간선의 개수밖에 떠오르지 않는다. 요소라 한다면 그 느낌은 더욱 작아지는 방향으로 나아가는 단위 물체 아닌가..

문제 이해 부족으로 인해 검색을 해보고 서로 관련 없이 완전 분리된 덩어리들의 개수를 찾는다는 것을 알았다.

 

예제 1번의 경우

의 형태를 갖는다.

 

 

작성된 코드는 DFS 로 완전 탐색을 하여 각 정점에 대한 visited = [] 를 채워나가되 연결이 새로 시작되는 시점에 countOfConnectedBundles 를 하나씩 늘려 그 누적합을 구한다.

 

 

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline
sys.setrecursionlimit(10_000)

def fnDFS(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            fnDFS(i)


if __name__ == "__main__":
    N, M = map(int, inputdata().split())
    uv_ls = [list(map(int, inputdata().split())) for _ in range(M)]
    # print(uv_ls)            # test print
    
    graph = [[] for _ in range(N + 1)]
    # print(graph)            # test print
    for uv in uv_ls:
        # print(uv)           # test print
        graph[uv[0]].append(uv[1])
        graph[uv[1]].append(uv[0])
    # print(graph)            # test print
    
    visited = [False] * (N + 1)
    countOfConnectedBundles = 0
    for i in range(1, N+1):
        if not visited[i]:
            fnDFS(i)
            countOfConnectedBundles += 1
    
    print(countOfConnectedBundles)

 

 

 

 

 

추가 하기

예제 입력 1 에 대한 풀이

import sys
inputdata = sys.stdin.readline
sys.setrecursionlimit(10_000)

def fnDFS(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            fnDFS(i)


if __name__ == "__main__":
    N, M = map(int, inputdata().split())
    uv_ls = [list(map(int, inputdata().split())) for _ in range(M)]
    print(f'uv_ls: {uv_ls}')            # test print
    
    graph = [[] for _ in range(N + 1)]
    print(f'graph: {graph}')            # test print
    for uv in uv_ls:
        print(f'uv: {uv}')           # test print
        graph[uv[0]].append(uv[1])
        graph[uv[1]].append(uv[0])
    print(f'graph: {graph}')            # test print
    
    visited = [False] * (N + 1)
    countOfConnectedBundles = 0
    for i in range(1, N+1):
        if not visited[i]:
            fnDFS(i)
            countOfConnectedBundles += 1
    
    print(countOfConnectedBundles)



# 6 5
# 1 2
# 2 5
# 5 1
# 3 4
# 4 6


# uv_ls: [[1, 2], [2, 5], [5, 1], [3, 4], [4, 6]]
# graph: [[], [], [], [], [], [], []]
# uv: [1, 2]
# uv: [2, 5]
# uv: [5, 1]
# uv: [3, 4]
# uv: [4, 6]
# graph: [[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]


# 2