[백준] 11724번 연결 요소의 개수 - DFS(stack, 재귀함수) (Python3)

문제와 입출력

예제 입출력

제한 조건과 설계

시간 제한과 메모리 제한

1. 무방향 그래프다.

2. 정점의 개수가 1000개 이하다.

3. 시간 제한과 메모리 제한이 굉장히 널널하다.

4. 2번과 3번을 고려했을 때 DFS가 좋아 보인다.

---

자연어 알고리즘

1. 무방향 그래프, 방문 테이블, 노드 목록를 생성한다.
2. 연결 요소의 개수 cnt를 0으로 초기화 하여 선언한다.
3. 노드 목록 하나 하나를 시작 지점으로 설정하여 DFS 탐색을 시도한다.
   • 노드가 이미 방문된 지점이면 -> continue
   • 노드가 아직 방문되지 않은 지점이면 -> DFS 탐색
4. DFS 탐색을 리스트 자료구조를 이용한 Stack 또는 재귀 함수를 이용한 Stack을 이용해 구현한다.
   • 가장 중요한 POINT: 스택에 PUSH된 순간 그 지점은 방문될 지점이므로 그 즉시 방문 테이블에 방문 처리를 한다.
5. DFS 탐색을 마쳤다면 cnt를 1 증가시킨다.
6. 3~5를 반복하다가 종료되면 cnt를 출력한다.

---

재귀 함수로 Stack을 구현하여 DFS 탐색

import sys

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

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
nodes = [n for n in range(1,n+1)]


for i in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

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

cnt = 0
for k in nodes:
    if visited[k] == True:
        continue
    dfs(graph,k,visited)
    cnt += 1
    
print(cnt)

---

리스트 자료구조로 Stack을 구현하여 DFS 탐색

import sys

input = sys.stdin.readline

n,m = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [False] * (n+1)
nodes = [n for n in range(1,n+1)]
stack = []

for i in range(m):
    u,v = map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

cnt = 0
stack = []
for k in nodes:
    if visited[k] == True:
        continue
    
    stack.append(k)
    visited[k] = True
    while stack != []:
        top = stack.pop()
        for i in graph[top]:
            if not visited[i]:
                stack.append(i)
                visited[i] = True

    cnt += 1

print(cnt)

---

세 줄 요약

1. sys.setrecursionlimit(10**6)은 재귀 함수의 깊이 한계를 늘려준다. DFS를 재귀함수로 구현할 때 꼭 사용하자.

2. 리스트 자료구조로 Stack을 구현하여 DFS 탐색을 할 수 있다.

3. is와 ==은 다르다. is는 Object를 비교하고 ==는 value를 비교한다.

+) DFS든 BFS든 stack 또는 Queue에 들어가는 순간 이미 방문 확정이다. 이때 반드시 바로 방문처리를 해야 한다.

---