오늘의 학습 키워드
DFS, Depth-First Search(깊이 우선 탐색)
그래프 탐색이란?
- 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것
- Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지
그러면 DFS란?
루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
- 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
- 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
- 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
- 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다.
- 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다.
깊이 우선 탐색(DFS)의 특징
- 자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
- 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.이를 검사하지 않으면 무한 루프에 빠질 수도 있다.
- 찾고자하는 답이 트리에서부터 멀어질 수록 DFS가 유리하다. (BFS에 비해)
깊이 우선 탐색(DFS)의 과정
- a 노드(시작 노드)를 방문한다.
- 방문한 노드는 방문했다고 표시한다.
- a와 인접한 노드들을 차례로 순회한다.
- a와 인접한 노드가 없다면 종료한다.
- a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
- b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
- b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
- 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
- 아직 방문이 안 된 정점이 없으면 종료한다.
- 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.
코드로 적용해보기
- 순서는 1번에서부터 시작하고, 번호가 낮은 순서부터 우선적으로 처리된다고 가정해보자.
- 그리고 노드를 방문 시 방문처리를 한다.
- 1번 시작 -> 2번으로 이동 -> 4번으로 이동 -> 6번으로 이동 -> 더 나아갈 수 없음 이전 노드로 백트래킹
- 4번 이웃 노드 없으므로 백트래킹 -> 2번 이웃 노드 없으므로 백트래킹 -> 1번의 또 다른 이웃 노드 3번으로 이동
- 3번 -> 5번으로 이동 -> 5번 이웃 노드 없으므로 백트래킹
- 3번 -> 7번으로 이동 -> 7번 이웃 노드 없으므로 백트래킹 -> 3번 이웃 노드 없으므로 백트래킹 -> 1번 복귀 -> 끝
탐색 순서 = 1->2->4->6->3->5->7
def dfs(graph, v, visited):
#v는 시작위치
visited[v] = True
print(v , end = ' ')
#현재 노드와 연결된 노드를 재귀적으로 호출
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
graph = [
[], # 0번 노드는 사용하지 않음
[2, 3, 7], # 1번 노드는 2, 3, 7번 노드와 연결
[1, 4, 6], # 2번 노드는 1, 4, 6번 노드와 연결
[1, 5, 7], # 3번 노드는 1, 5, 7번 노드와 연결
[2, 6], # 4번 노드는 2, 6번 노드와 연결
[3, 7], # 5번 노드는 3, 7번 노드와 연결
[2, 4], # 6번 노드는 2, 4번 노드와 연결
[1, 3] # 7번 노드는 1, 3번 노드와 연결
]
#각 노드가 방문한 정보를 리스트 자료형으로 표현
visited = [False] * 9
print("방문순서")
dfs(graph, 1, visited)출력 :
방문순서
1 2 4 6 3 5 7
- graph를 저렇게 표현한 이유는 그래프의 인접 리스트 (adjacency list) 방식으로 표현하기 위해서이다.
- 인접 리스트는 그래프를 저장하는 방법 중 하나로, 각 노드에 연결된 다른 노드들을 리스트 형태로 저장하는 방식
- 이 방식은 메모리 효율성이 좋아서, 그래프의 간선 수가 많지 않을 때 특히 유용합니다.
- 인접 리스트 방식은 각 노드에 대해 연결된 모든 노드를 리스트에 저장
- 이 방식은 그래프가 희소할 때 (즉, 간선의 수가 적을 때) 메모리 사용량이 효율적이며, 간선의 수가 많을 때는 인접 행렬보다 비효율적
오늘의 문제
백준 24479번
https://www.acmicpc.net/problem/24479
문제 설명
입출력 예
문제 생각해보기
위 입출력 예시에 따르면 결론적으로 5개의 정점, 5개의 간선인데
- 1 ~ 4까지의 노드 중 1번과 3번 사이 간선이 없다.
- 그리고 5번 노드는 아무 노드와 연결되어 있지않다.
DFS 탐색 순서
오름차순 방문: DFS 탐색 시 인접 정점들을 오름차순으로 방문.
- 시작 노드는 1번이다. 1번을 방문했으므로 방문 순서는 1.
- 노드 1에 연결된 노드는 2와 4인데, 오름차순으로 방문하므로 2번 노드를 먼저 방문.
- 노드 2를 방문했으므로 방문 순서는 2.
노드 2에 연결된 노드는 1, 3, 4이다. 이미 1번은 방문했으므로 3번을 방문. - 노드 3을 방문했으므로 방문 순서는 3.
노드 3에 연결된 노드는 2와 4이다. 이미 2번은 방문했으므로 4번을 방문. - 노드 4를 방문했으므로 방문 순서는 4.
노드 4에 연결된 노드는 1, 2, 3이다. 모두 방문했으므로 더 이상 갈 곳이 없음. - 노드 5는 연결된 간선이 없어서 방문할 수 없음. 따라서 방문 순서는 0.
1. 기본 설정 및 입력 처리
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) # 각 정점의 방문 순서를 저장하는 리스트 (0이면 방문하지 않음)
sys.setrecursionlimit(10 ** 6): 재귀 깊이를 늘려 깊이 우선 탐색(DFS) 중 스택 오버플로 방지input = sys.stdin.readline: 빠른 입력을 위해 사용, 사용하지 않으면 런타임 에러n, m, r = map(int, input().split()): 정점의 수, 간선의 수, 시작 정점을 입력받음graph = [[] for _ in range(n + 1)]: 그래프를 인접 리스트로 표현하기 위해 초기화visited = [0] * (n + 1): 각 정점이 방문된 순서를 저장할 리스트, 초기값은 0
2. 깊이 우선 탐색(DFS) 함수 정의
order = 1 # 방문 순서 카운터
def dfs(graph, v, visited):
global order
visited[v] = order # 방문하면 순서 기록
for i in graph[v]: # 현재 정점과 연결된 모든 정점을 순회
if visited[i] == 0: # 방문하지 않은 정점이라면
order += 1
dfs(graph, i, visited) # 재귀적으로 탐색visited[v] = c: 정점 v를 방문했을 때 방문 순서를 저장for i in graph[v]: 정점 v에 연결된 모든 인접 정점을 순회if visited[i] == 0: 아직 방문하지 않은 정점만 탐색- dfs 함수가 스스로를 다시 호출하면서 깊이 우선 탐색을 진행
3. 간선 정보 입력 및 그래프 구성
for i in range(m):
a, b = map(int, input().split()) # 간선 정보 입력
graph[a].append(b)
graph[b].append(a) # 무방향 그래프이므로 양쪽에 간선 추가
for i in range(m): m개의 간선 정보를 입력받음- append()는 파이썬의 리스트(list) 자료형에서 사용되는 메서드로, 리스트의 끝에 새로운 요소를 추가하는 역할
- graph[a].append(b): 정점 a의 인접 리스트에 정점 b를 추가.
graph[b].append(a): 정점 b의 인접 리스트에 정점 a를 추가.
입력 예시에 따르면
- graph[1]에 4와 2를 추가 → graph[1] = [4, 2]
- graph[2]에 1, 3, 4를 추가 → graph[2] = [1, 3, 4]
- graph[3]에 2와 4를 추가 → graph[3] = [2, 4]
- graph[4]에 1, 2, 3을 추가 → graph[4] = [1, 2, 3]
4. 인접 리스트 정렬
for i in range(n + 1):
graph[i].sort() # 오름차순으로 인접 정점을 정렬 5. 깊이 우선 탐색 시작 및 결과 출력
dfs(graph, r, visited)
for i in range(1, n + 1):
print(visited[i])dfs(graph, r, visited): 시작 정점 r에서 DFS 수행print(visited[i]): 정점 i의 방문 순서를 출력
전체 풀이
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) # 방문 순서 저장. 0이면 방문 X
order = 1 # 방문 순서 변수
def dfs(graph, v, visited):
global order
visited[v] = order # 방문하면 순서 나타내기
for i in graph[v]:
if visited[i] == 0: # 방문 안 한 노드이면
order += 1
dfs(graph, i, visited) # dfs 재귀
# m개의 연결된 간선 정보 입력받기
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
# 오름차순으로 인접 노드 방문하기 위해 정렬
for i in range(n + 1):
graph[i].sort()
dfs(graph, r, visited)
for i in range(1, n + 1):
print(visited[i])오늘의 회고
🔥 dfs의 개념부터 이해하느라 시간이 오래 걸렸다. 아직 이해가 잘 안된 것 같다. 문제를 더 풀어보면서 적용해야할듯? bfs와 비교하면서도 풀어봐야 될 것 같다.
🔥 런타임에러가 나지않기 위에 하는 sys 설정, append 함수에 대해서 몰라 찾아보았다. 아직 혼자 풀기 어려운 점이 많다.
참고 문헌
[파이썬 알고리즘] 쉽게 이해하는 DFS 알고리즘 (정의, 특징, 코드)
[알고리즘] 깊이 우선 탐색(DFS)이란
[알고리즘] 너비 우선 탐색(BFS)이란
