TIL) 11724 연결 요소의 개수(BFS/DFS)

이 포스팅은,
1. 미래의 내가 다시 이 문제를 풀고자 할 때 과거의 내가 어떻게 문제를 해결했었는지 알려주기 위해서
2. 같은 문제를 풀고 있는 사람에게 아이디어를 제공하기 위해서
작성되었습니다.

🎈 연결 요소의 개수

백준 11724 연결 요소의 개수 : https://www.acmicpc.net/problem/11724

💡 아이디어

• 연결된 노드를 구해주는 간단한 문제이다.
• DFS와 BFS로 각각 구현할 수 있고 DFS와 BFS의 특징이 잘 나타난다.

🎪 DFS로 구현

# 연결 요소의 개수 - dfs로 푼 버전

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

visited = [False]*(N+1)
graph = [[] for _ in range(N+1)]
for _ in range(M):
    i, j = map(int, input().split())
    graph[i].append(j)
    graph[j].append(i)


def dfs(i):
    visited[i] = True
    for num in graph[i]:
        if not visited[num]:
            dfs(num)

cnt = 0
for i in range(1, N+1):
    if not visited[i]:
        dfs(i)
        cnt += 1
print(cnt)

👉 DFS

• 함수 밖에서 visited == True인 노드는 이미 방문했기 때문에 dfs로 확인하지 않는다.
• dfs()로 들어오면 방문 처리를 해주고 해당 노드와 연결되어 있는 노드를 다시 dfs()로 확인해주어야 한다.
• 이 과정에서 재귀함수가 사용된다.

🎡 BFS로 구현

def bfs(start):
    q = deque()
    q.append(start)
    visited[start] = True
    while q:
        x = q.popleft()
        for y in adj_list[x]:
            if visited[y] == False:
                q.append(y)
                visited[y] = True

👉 BFS

• 함수를 제외한 부분은 DFS와 완전히 일치한다.
• bfs() 함수 역시 방문처리를 해준다.
• dfs()와 다른 점은 매개변수로 받아온 노드를 queue에 넣어주면서 시작한다는 점이다.
• 받아온 노드를 queue에 넣어주고 while문을 돌린다.
• 큐에 있는 노드를 pop해서 해당 노드에 연결되어있는 노드가 이전에 방문한 적 없는 노드일 경우 queue에 넣어주고 방문처리해준다.
• 이 과정에서 deque가 사용된다.