DFS(Depth-First-Search)
깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
*그래프란?
노드와 간선으로 표현되며 이때 노드를 정점이라고도 말한다.
또한 두 노드가 간선으로 연결되어 있으면, "두 노드가 인접하다" 라고 표현한다.
그래프의 기본구조
그래프의 종류
무방향 그래프
간선을 통해 양방향으로 이동할 수 있는 그래프
G(A,B)는 G(B,A)와 동일
방향 그래프
간선에 방향이 존재하는 그래프
G(A,B)와 G(B,A)는 다름
가중치 그래프
간선에 비용 또는 가중치가 할당된 그래프
'네트워크' 라고도 함
연결 그래프
무방향 그래프에서 모든 정점쌍들에 대해 항상 경로가 존재하는 그래프
비연결 그래프
무방향 그래프에서 특정 정점쌍들에 경로가 존재하지 않는 그래프
순환 그래프
단순 경로의 시작 정점과 종료 정점이 동일한 경우
※ 단순 경로(Simple Path) : 반복되는 정점이 없는 경로
비순환 그래프
순환이 없는 그래프
프로그래밍에서 그래프는 크게 2가지 방식으로 표현할 수 있다.
1. 인접 행렬(Adjacency Matrix)
2차원 배열로 그래프의 연결 관계를 표현하는 방식
- 파이썬은 2차원 리스트로 구현할 수 있다.
연결이 되어 있지 않은 노드끼리는 무한의 비용이라고 작성한다.
실제 코드에서는 논리적으로 정답이 될 수 없는 큰 값 중에서 999999999, 987654321 등의 값으로 초기화하는 겨우가 많다. 이렇게 그래프를 인접 행렬 방식으로 처리할 때는 다음과 같이 데이터를 초기화한다.
#무한의 비용 선언
INF = 999999999
#2차원 리스트를 이용해 인접 행렬 표현
#자바에서는 2차원 배열로 구현하면된다.
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]2. 인접 리스트(Adjacency List)
인접 리스트 방식에서는 다음 그림처럼 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다.
Linked List를 사용하여 구현한다. C++이나 JAVA는 해당 자료구조를 위한 표준 라이브러리를 제공하는 반면, 파이썬은 기본 리스트 자료형이 append()와 메소드를 제공하므로, 전통적인 프로그래밍 언어에서의 배열과 연결 리스트의 기능을 모두 기본으로 제공한다...
따라서 파이썬에서는 단순히 2차원 리스트를 이용하면된다..
비교
메모리 측면에서 인접 행렬 방식은 모든 관계를 저장하므로, 노드 개수가 많을 수록 메모리가 불필요하게 낭비된다는 단점이 있다.
반면, 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다.(연결된 데이터를 하나씩 확인해야 하기 때문)
DFS
특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.
스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
다음 그래프를 탐색해보자
public class main
{
public static void dfs(int[][] graph, int v, boolean[] visited) {
//현재 노드 방문처리
visited[v] = true;
System.out.println(v);
//현재 노드와 연결된 다른 노드를 재귀적으로 방문
for(int i = 0; i < graph[v].length; i++) {
int n = graph[v][i];
if(!visited[n]) {
dfs(graph, n, visited);
}
}
}
public static void main(String[] args)
{
int[][] graph = {
{},
{2,3,8},
{1,7},
{1,4,5},
{3,5},
{3,4},
{7},
{2,6,8},
{1,7}
};
boolean[] visited = new boolean[9];
for(int i = 0; i < visited.length; i++) {
visited[i] = false;
}
dfs(graph, 1, visited);
}
}결과
1
2
7
6
8
3
4
5DFS 실전문제. 음료수 얼려 먹기
N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상,하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 중졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 다음의 4 x 5 얼음 틀 예시에서는 아이스크림이 총 3개 생성된다.
00110
00011
11111
00000
입력조건
-- 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다.(1 <= N, M <= 1,000)
-- 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다.
-- 이때 구멍이 뚫려이쓴 부분은 0, 그렇지 않은 부분은 1
출력조건
-- 한 번에 만들 수 있는 아이스크림의 개수를 출력한다.
풀이
공간이 상, 하, 좌, 우로 연결되어 있다고 표현할 수 있으므로, 그래프로 모델링 할 수 있다.
3 x 3 크기의 얼음틀이 있다고 가장해보자.
이는 DFS로 해결할 수 있다.!
- 특정한 지점의 주변 상,하,좌,우 를 살펴본 뒤에 주변 지점 중에서 값이 '0'이면서 아직 방문하지 않은 지점이 있다면 해당 지점을 방문한다.
- 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행하면, 연결된 모든 지점을 방문할 수 있다.
- 1 ~ 2번의 과정을 모든 노드에 반복하며 방문하지 않은 지점의 수를 센다.
import java.util.*;
public class DFSEX {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[][] graph = new int[n][m];
int result = 0;
for(int i = 0; i < n; i++){
String number = sc.next();
for(int j = 0; j < m; j++) {
graph[i][j] = Integer.valueOf(String.valueOf(number.charAt(j)));
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
//음료수를 따르면 true
if(dfs(i, j, n, m, graph) == true) {
result++;
}
}
}
System.out.print(result);
}
public static boolean dfs(int x, int y, int n, int m, int[][] graph) {
// 주어진 범위를 벗어나는 경우 즉시 종료
if(x <= -1 || y <= -1 || x >= n || y >= m) {
return false;
}
// 현재 노드를 방문하지 않았다면
if(graph[x][y] == 0) {
graph[x][y] = 1;
//음료를 한번 따를 때 상하좌우로 흐르므로, 음료수가 부어진것만 크게 체크하며, 끊기는지를 탐색함(방문처리)
//상, 하, 좌, 우의 위치도 모두 재귀적으로 호출
dfs(x-1, y, n, m, graph);
dfs(x+1, y, n, m, graph);
dfs(x, y-1, n, m, graph);
dfs(x, y+1, n, m, graph);
return true;
}
//주어진 범위 안에서, 방문한 경우
return false;
}
}
음료수를 따랐던 경우를 세서 출력하면 되므로,
한번 음료를 따르면 어디까지 들어가는지(막히지 않는지)를 확인하면서 음료가 찬 곳은 방문처리를 하고, 카운트한다.
참고 : 이것이 코딩테스트다 with 파이썬 - 나동빈
