[백준 문제] 11724번 연결 요소의 개수 (파이썬)

정리

연결 요소(Connected Componet)는 각각의 그래프를 말한다.
여기서 문제는 맞으나 백준에서는 런타임 또는 시간초과가 나오는데 좀더 깊게 파봐야겠다.

# N : 정점 갯수, M : 간선 갯수, V : 시작 정점 번호
N, M = map(int, input().split())
# 0으로 왼쪽 위쪽을 둘러쌈(인덱스와 번호가 헷갈려서)
matrix = [[0] * (N + 1) for _ in range(N + 1)]

# 간선 갯수로 인접 행렬 만들기
for _ in range(M):
    link = list(map(int, input().split()))
    matrix[link[0]][link[1]] = 1
    matrix[link[1]][link[0]] = 1


# 너비 우선 탐색(Breadth First Search)
def bfs(start):
    # 큐 (빨대모양이라고 생각하면 편함)
    queue = [start]
    # 발자취 리스트
    foot_prints = [start]

    # 큐가 공 리스트가 될때까지(할게없을때까지)
    while queue :
        # 큐에서 현재 가장 처음에 들어간거(인덱스 0 인거)를 current_node에 넣는다
        # 큐는 공리스트가 된다.
        current_node = queue.pop(0)
        # 돌면서 끝에 결국 queue가 아무것도 없게 된다.
        for search_node in range(len(matrix[current_node])):
            if matrix[current_node][search_node] and search_node not in foot_prints:
                foot_prints += [search_node]
                queue += [search_node]
    return sorted(foot_prints) # 솔팅해서 저장

# 리스트에 BFS를 이용해서 모든 정점에성의 순서를 sorting해서 저장
arr = []
for i in range(1, N+1) :
    arr.append(bfs(i))

# 솔팅해서 저장한것을 집합을 이용해서 합치고 그거의 갯수 출력
remove_dup = list(set(map(tuple, arr)))
print(len(remove_dup))

[백준 문제] 11724번 연결 요소의 개수 (파이썬)

Share this post