백준 11724 : 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

BFS 기본 구조를 이해하고 있는지 물어보는 문제.

앞으로 역량 테스트 준비하면서 github도 사용해봐야겠다.

 

1. BFS

 연결 요소들을 graph 에 담아서 너비 탐색을 시행한다. 연결 뭉치들이 여러개 있을 수 있으므로 각 노드를 전부 탐색하되, 방문 리스트를 활용해 이미 방문한 적이 있는 것은 같은 뭉치에 속해 있으므로 패스하는 방식으로 코드를 구현했다.

 

2. 전체코드

메모리 184288 KB, 시간 784 ms

SW 코딩 테스트 준비를 다시 하면서 몸풀기로 풀어보았다.

 

N, M = map(int, input().split())

graph = [[] for _ in range(N+1)]
count = 0
for i in range(M):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

# 낮은 순서대로 정렬해주자
# 일반적인 너비 탐색은 낮은 숫자부터 진행하기 때문에
for i in range(1, N+1):
    graph[i].sort()

def bfs(arr):
    global count
    # 너비 탐색이 끝난 뭉치 +1
    visited = [False for _ in range(N + 1)]
    for i in range(1, len(arr)):
        if not visited[i] :
            visited[i] = True
            count += 1
            q = [arr[i]]
            while q :
                x = q[0]
                del q[0]
                for j in x :
                    if not visited[j] :
                        visited[j] = True
                        q.append(arr[j])
    return
bfs(graph)
print(count)

 

https://github.com/HPYoo/swcodingtest/blob/main/prob11724.py

GitHub - HPYoo/swcodingtest: 코딩테스트 대비 연습