이게 왜 돌아가? 너 뭐 돼?
이코테를 풀면서 DFS랑 BFS에 대해서 공부해본 적이 있는데, 오랜만에 보려니까 다시 다 처음 본 기분이었다..뭔가 풀긴했는데 이게 왜 돌아가지라는 생각
백준 24479번 문제 풀이
문제
오늘도 서준이는 깊이 우선 탐색(DFS) 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.
N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 깊이 우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자.
깊이 우선 탐색 의사 코드는 다음과 같다. 인접 정점은 오름차순으로 방문한다.
dfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점
visited[R] <- YES; # 시작 정점 R을 방문 했다고 표시한다.
for each x ∈ E(R) # E(R) : 정점 R의 인접 정점 집합.(정점 번호를오름차순으로 방문한다)
if (visited[x] = NO) then dfs(V, E, x);
}[입력]
첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다.
다음 M개 줄에 간선 정보 u, v가 주어지며 정점 u와 정점 v의 가중치 1인 양방향 간선을 나타낸다. (1 ≤ u < v ≤ N, u ≠ v) 모든 간선의 (u, v) 쌍의 값은 서로 다르다.
문제 해석하기
- 일단 dfs가 무엇인지 부터 파악하기
- dfs는 주로 재귀함수와 스택을 사용하는데, 예시에서 재귀함수를 사용했으니 해당 방식을 이용해서 구현하려고 함
- n,m,r을 입력받기 => map을 이용해서 입력 코드 구현
- graph를 생성하기 => 노드와 간선이 입력될 수 있는 그래프를 생성해서 탐색이 가능하도록 함
- dfs 함수 생성하기
- 파라미터로는 visited, r, graph를 넣어주어 시작 노드에서부터 탐색할 수 있도록 함
- 탐색을 하다가 이미 방문한 노드인 경우 다른 노드로 이동해서 탐색하도록 구현(재귀함수 사용)
- 인접 정점을 오름차순으로 확인하기 위해서 graph를 sort함수를 이용해 오름차순으로 만들어줌
- dfs 실행 및 답 출력하기
문제 풀이 중 문제점
1) 재귀 깊이가 깊어져서 발생할 수 있는 문제 해결하기
재귀 깊이가 깊어져서 발생하는 RecursionError를 방지
DFS처럼 깊은 재귀 호출을 사용하는 경우에는 알고리즘에서 기본적인 제한(1000)을 초과하는 경우 설정을 통해서 더 깊은 깊이까지 탐색할 수 있다.2) input = sys.stdin.readline
입력 데이터가 많은 경우에는 input() 함수 대신에 readline을 사용하면 입력 속도가 빨라져서 시간초과 문제를 해결할 수 있음
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
n, m, r = map(int, input().split())
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
cnt =1
def dfs(graph,v,visited):
global cnt
visited[v] = cnt
for i in graph[v]:
if visited[i]==0:
cnt+=1
dfs(graph,i,visited)
for i in range(m):
u,v = map(int,input().split())
graph[u].append(v)
graph[v].append(u)
for i in range(n+1):
graph[i].sort()
dfs(graph,r,visited)
for i in range(n+1):
if i!=0:
print(visited[i])
DFS란?
일단 DFS가 무엇인지에 대해서 알고 넘어가는것이 좋을 것 같아서 내용 정리를 해보았다.
- DFS(Depth First Search)는 그래프나 트리 구조에서 데이터를 탐색하거나 순회하는 대표적인 알고리즘
- DFS는 깊이 우선으로 탐색을 진행한다. 즉, 현재 탐색 중인 노드에서 갈 수 있는 가장 깊은 곳까지 탐색한 후, 더 이상 깊이 갈 수 없으면 한 단계씩 뒤로 되돌아와서 다음 노드를 탐색
DFS의 동작 방식
- 시작 노드 선택: 탐색을 시작할 노드를 선택한다
- 방문 기록: 방문한 노드는 방문 여부를 기록하여, 다시 방문하지 않도록 한다.
=> visited[]를 이용해서 visit했는지 안했는지 여부를 Boolean으로 처리함- 인접 노드 탐색: 현재 노드의 인접 노드 중 방문하지 않은 노드가 있으면 그 노드로 이동하고 탐색을 반복한다.
=> 주로 스택이나 재귀함수를 사용해서 탐색을 함- 백트래킹: 더 이상 방문할 인접 노드가 없으면 이전 노드로 되돌아가서 다른 경로를 탐색
- 반복: 모든 노드를 방문할 때까지 탐색을 반복한다
오늘의 회고
오랜만에 깊이우선탐색과 관련한 코드를 작성하면서 역시 1일 1코테를 해야하는구나를 느꼈던 것 같다. 확실히 알고리즘을 오랜만에 보니까 어떤 식으로 접근해야 할지 조금 망설여졌다. DFS와 BFS모두 다시 공부해보면서 구현해볼 수 있어서 좋은 시간이었다.
