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가 사용된다.
Author And Source
이 문제에 관하여(TIL) 11724 연결 요소의 개수(BFS/DFS)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mongle/TIL-11724-연결-요소의-개수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)