[백준] 11724번: 연결 요소의 개수 (sol.X)

풀이시간: X

1. 나의 풀이

• 인접행렬로 그래프 상황을 그린다.
• 그래프 탐색을 하면서 서로 연결 여부를 판단한다.
• bfs로 탐색을 하면서 큐가 비었지만 탐색할 곳이 남았다면 +1 하고 남은 곳 방문 및 탐색 반복

2. 또다른 풀이

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

N, M = map(int, input().split())
adj = [[0] * N for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: x - 1, map(int, input().split()))
    adj[a][b] = adj[b][a] = 1

ans = 0
chk = [False] * N

def dfs(now):
    for nxt in range(N):
        if adj[now][nxt] and not chk[nxt]:
            chk[nxt] = True
            dfs(nxt)

for i in range(N):
    if not chk[i]:
        ans += 1
        chk[i] = True
        dfs(i)

print(ans)

• chk 배열을 False로 초기화
• 반복문을 돌면서 False를 만나면 +1 하고 BFS를 돌린다.
• 방문을 했을 시에는 chk 배열 해당 노드를 True로 바꿔준다.
• 한 탐색이 완료됐을 때, chk 배열 False 탐색

3. 보완할 것

• dfs, bfs 풀이 형태 익히기
• 방문시에 방문을 했다는 것을 남겨야 한다. (무한 루프 방지)
• 빠른 입출력 함수 input = sys.stdin.readline
• 재귀 한도 해체 sys.setrecursionlimit(10 ** 6)