[백준] 11724번 : 연결 요소의 개수 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

11724번: 연결 요소의 개수

 

1. 문제 설명

2. 풀이과정

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 너비 우선 탐색에서 deque 자료구조를 활용하기 위해 deque 모듈을 불러온다. from collections import deque
3. 정점과 간선의 수를 입력받는다. N, M = map(int, sys.stdin.readline().split())
4. 그래프 정보를 저장할 리스트를 생성하고 graph = list()
5. 각 정점별 연결된 정점을 저장할 리스트를 안에 추가해준다. for i in range(N): graph.append([])
6. 간선의 수만큼 반복하며 for i in range(M)
7. 정점 두개를 입력받고 v1, v2 = map(int, sys.stdin.readline().split())
8. 각 정점의 정보를 추가한다. graph[v1 - 1].append(v2 - 1)
9. 정보를 추가할 때는 정점 번호를 인덱스로 생각하여 추가한다. graph[v2 - 1].append(v1 - 1)
10. 요소의 개수를 구할 때 사용할 너비 우선 탐색 알고리즘을 함수로 구현한다. def bfs(start)
11. 각 정점을 탐색했는지에 대한 정보를 저장할 리스트를 생성하고 탐색 안한 표시로 초기화한다. result = [False] * N
12. 요소의 개수를 저장할 변수를 생성하고 초기화한다. count = 0
13. 각 정점을 하나씩 불러오며 for i in range(N)
14. 만약 해당 정점이 아직 탐색되지 않은 정점이라면 if (not result[i])
15. 해당 정점을 시작으로 너비 우선 탐색을 진행한다. bfs(i)
16. 너비 우선 탐색을 마치면 요소를 하나 찾은 것과 마찬가지이므로 요소 개수를 1 증가시킨다. count += 1
17. 모든 정점에 대한 탐색이 끝났으면 요소의 개수를 출력한다. print(count)

bfs(start) 함수

1. 시작 정점을 탐색한다. result[start] = True
2. 탐색을 시작하는 정점을 저장할 deque을 생성한다. queue.deque()
3. 시작 정점을 탐색을 시작하는 정점에 추가한다. queue.append(start)
4. 탐색할 정점이 있으면 반복한다. while (queue)
5. 탐색할 정점 deque에서 가장 앞 정점을 새로운 시작 정점으로 가져온다. start = queue.popleft()
6. 시작 정점과 연결된 정점을 하나씩 추출하며 for i in graph[start]
7. 만약 추출한 정점이 탐색하지 않은 정점이라면 if (not result[i])
8. 해당 정점을 탐색하고 result[i] = True
9. 탐색을 시작하는 정점 deque에 추가한다. queue.append(i)

반응형

3. 소스코드

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())

graph = list()
for i in range(N):
    graph.append([])

for i in range(M):
    v1, v2 = map(int, sys.stdin.readline().split())
    graph[v1 - 1].append(v2 - 1)
    graph[v2 - 1].append(v1 - 1)

def bfs(start):
    result[start] = True
    queue = deque()
    queue.append(start)

    while (queue):
        start = queue.popleft()
        for i in graph[start]:
            if (not result[i]):
                result[i] = True
                queue.append(i)

result = [False] * N
count = 0
for i in range(N):
    if (not result[i]):
        bfs(i)
        count += 1

print(count)