[BOJ] 11724번 연결 요소의 개수 / 사용언어 : 파이썬(python)

※ 문제링크

11724번: 연결 요소의 개수

※ 참고사이트

[그래프] 연결 요소

해당 문제는 BFS로 해결할 수 있는 문제였다. 우선 연결 요소의 개념을 알아야 했기에 구글링을 통해 해당 개념을 확인하고, 문제를 해결하였다. 처음에 문제를 해결할때 간선이 없는 정점에 대해서는 고려하지 않아 오답을 받았다. 이후에는 해당 부분을 수정해주고, 생각한대로 구현했더니 문제를 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다.

1. 입력받은 값들을 딕셔너리를 활용하여 그래프를 구현한다.

2. 각 정점 방문여부를 확인할 체크리스트를 리스트로 구현하고, 간선이 없는 정점들을 그래프에 추가해준다.

3. 간선으로 연결된 정점들을 확인할 BFS함수를 작성한다.

4. 반복문을 통해 그래프내의 모든 정점들을 확인하고, 조건을 충족하면 cnt에 +1을 해준다.

5. 반복문을 모두 수행한 수 cnt값을 출력한다.

+ 시간 단축을 위해 입력값을 sys함수로 입력받았다.(사용시 개행문자에 유의하자)

 

import sys
from collections import deque

def bfs(number):
    queue = deque(graph[number])
    check[number] = True
    while queue:
        check_number = queue.popleft()
        if check[check_number] == False:
            check[check_number] = True
            queue.extend(graph[check_number])

# input = sys.stdin.readline
N, M = map(int, input().split()) # N :  정점의 개수 / M : 간선의 개수
graph = dict()
for _ in range(M):
    key, value = map(int, input().split())
    if key != value:
        if key not in graph:
            graph[key] = [value]
        else:
            graph[key].append(value)
        if value not in graph:
            graph[value] = [key]
        else:
            graph[value].append(key)

check = [False for _ in range(N+1)]
cnt = 0
for i in range(1, N+1):
    if i not in graph:
        graph[i] = []
for num in graph:
    if check[num] == False:
        bfs(num)
        cnt += 1
print(cnt)

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.