백준 11720 연결 요소의 개수 (파이썬)

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

 

첫번째 풀이 

처음에 서로소 방법인 줄 알고 그래프 이론의 서로소 구하는 방법을 이용하여 구현하려고 했습니다. 코드는 다음과 같습니다.

import sys
#특정 원소가 속한 집합 찾기
def findParent(parent, v):
    # 루트노드가 아니라면 루트 노드를 찾을 때 까지 재귀적 호출
    if parent[v] != v:
        parent[v] = findParent(parent, parent[v])
    return parent[v]

#부모 합치기
def unionParent(parent, v1, v2):
    v1 = findParent(parent, v1)
    v2 = findParent(parent, v2)
    if v1 < v2:
        parent[v2] = v1
    else:
        parent[v1] = v2
    return parent
def solve():
    N, M = map(int, input().split())
    parent = [0] * (N+1) #부모 테이블 초기화

    for i in range(1, N+1):
        parent[i] = i #부모를 자기 자신으로 설정

    for i in range(M):
        v1, v2 = map(int, input().split())
        parent = unionParent(parent, v1, v2)

    cnt = 0
    parentList = []
    for i in range(1, N + 1):
        if parent[i] not in parentList:
            parentList.append(parent[i])

    print(len(parentList))
    return

if __name__ =="__main__":
    input = sys.stdin.readline
    solve()

그런데 예제 2에서 6번 정점의 부모가 안바뀌는 것을 확인하고 업데이트가 서로소로 구하면 업데이트가 안되는 것을 알 수 있었습니다.

그래서 BFS를 이용하여 연결 개수를 세었습니다.

 

두번째 풀이

BFS를 활용하여 문제를 해결했습니다.

import sys
from collections import deque
#특정 원소가 속한 집합 찾기
def BFS(arr, start, visited):
    q = deque([start])
    visited[start] = 1
    cnt = 0
    while q:
        x = q.popleft()
        for end in arr[x]:
            if not visited[end]:
                q.append(end)
                visited[end] = 1
                cnt += 1
    return cnt
def solve():
    if M == 0:
        print(N)
        return

    for i in range(M):
        v1, v2 = map(int, input().split())
        arr[v1].append(v2)
        arr[v2].append(v1)

    visited = [0] * (N + 1)
    cnt = 0
    for i in range(1, N+1):
        if arr[i]:
            if not visited[i]:
                cnt += BFS(arr, i, visited)
    print(N-cnt)
    return

if __name__ =="__main__":
    input = sys.stdin.readline
    N, M = map(int, input().split())
    arr = [[] for i in range(N + 1)]
    solve()

 

후기

단순하게 BFS를 이용하여 개수만 파악하면 되는 줄 알았는데 예외가 발생하였습니다.

 

반례

6 2

1 2

1 3

 

1 - 2 - 3, 4, 5, 6

 

정답 4

 

1. 간선의 개수가 0개이면 0을 출력하는 것이 아니라 정점의 개수를 출력해야 합니다. 이는 간선이 없는 경우 정점의 개수를 연결된 개수로 간주하기 때문입니다.

 

2. 총 정점의 개수 - (BFS로 확인한 연결된 정점의 개수-1)

 

처음에 쉬운 문제인 줄 알고 섣불리 풀었다가 반례 때문에 조금 고생한 문제입니다. 현재 백준 골드4 이긴 하지만 실버 문제도 한번에 풀지 못하는 것으로 봐선 아직 실력이 낮은 실버인 것 같습니다 ㅠ