Notice
Recent Posts
Recent Comments
Link
nathan_H
[Algorithms] DFS, BFS 개념과 구현 본문
시작하기
알고리즘을 풀다보면 그래프 자료구조를 사용하는 경우가 많고, 그래프 자료구조를 사용하는 문제의 상당수는 DFS, BFS을 구현해 문제를 해결하는 경우가 많다. 그리고 문제의 난이도가 올라갈수록 단순한 DFS, BFS가 아닌 다양한 형태로 변형한 DFS, BFS을 요구한다. 그래서 DFS, BFS 개념과 몇가지 유형을 통해 한번 DFS, BFS을 뿌시고자 한다.
Graph 자료형
그래프 자료형의 경우 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多의 관계 를 가지는 원소들을 표현하기 위한 자료구조로 객체의 정점과 객체를 연결하는 간선의 집합이다.
그래프
객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합
𝐺 = (𝑉,𝐸)
− 𝑉는 그래프에 있는 정점들의 집합
− 𝐸는 정점을 연결하는 간선들의 집합
그래프를 표현하는 방법은 다양하고 인접행렬, 연결 자료구조를 통해 추상적으로 구현할 수 있다.
그래프 순회
- 그래프 자료형의 경우 어려운 관계를 표현할 수 있는 장점을 가지고 있지만, 다른 자료구조에 비해 각 정점을 순회하는 방법이 비교적 까다롭다.
- 그래프 순회 방법은 아래 두 가지 접근법으로 진행.
- 깊이 우선 탐색
- 한 지점을 골라서 팔수 있을때 까지 계속 해서 깊게 파다가 아무리 땅을 파도 물이 나오지 않으면, 밖으로 나와 다른 지점을 골라서 다시 깊게 땅을 파는 방법
- 너비 우선 탐색
- 여러 지점을 고르게 파보고 물이 나오지 않으면,파놓은 구덩이 들을 다시 좀 더 깊게 파는 방법
- 참고로 트리 자료구조에서도 탐색 알고리즘으로 깊이 우선, 넓이 우선이 사용된다.
- 깊이 우선 탐색
깊이 우선 탐색
- 깊이 우선 탐색은 앞에서 언급했듯이 한 지점을 골라 계속 깊이 파서 순회한 후 지점의 끝에 도달할 때 다른 지점을 순회하는 방법이다.
- 순회 방법을 정리하면 아래와 같다.
순회 방법
- 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
- 더 이상 갈 곳이 없게 되면,가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴
- 다른 방향의 간선으로 탐색을 계속 반복하여 결국 모든 정점을 방문 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가서
- 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택과 재귀를 활용해 구현
실행 순서 및 코드
깊이 우선 탐색의 수행 순서
(1)시작 정점 𝑣를 결정하여 방문한다.
(2)정점 𝑣에 인접한 정점 중에서
- 방문하지 않은 정점 𝑤가 있으면, 정점 𝑣를 스택에 push하고 𝑤를 방문한다. 그리고 𝑤를 𝑣로 하여 다시 (2)를 반복한다.
- 방문하지 않은 정점이 없으면, 탐색의 방향을 바꾸기 위해서 스택을 pop하여 받은 가장 마지막 방문 정점을 𝑣로 하여 다시 (2)를 수행한다.
(3) 스택이 공백이 될 때까지 (2)를 반복한다.
코드
- 위 dfs를 스택으로 구현한 코드.
import java.util.ArrayList;
import java.util.Stack;
public class DfsBfsPractice {
private static ArrayList<ArrayList<Integer>> graph;
private static boolean[] visited;
public static void main(String[] args) {
graph = new ArrayList<>();
visited = new boolean[10];
for (int i = 0; i < 10; i++) {
graph.add(new ArrayList<>());
}
graph.get(1).add(3);
graph.get(1).add(2);
graph.get(2).add(1);
graph.get(2).add(5);
graph.get(2).add(4);
graph.get(4).add(2);
graph.get(4).add(8);
graph.get(5).add(4);
graph.get(3).add(1);
graph.get(3).add(7);
graph.get(3).add(6);
graph.get(6).add(3);
graph.get(6).add(9);
graph.get(7).add(3);
graph.get(8).add(4);
graph.get(9).add(6);
dfsStack(1);
}
private static void dfsStack(int r) {
Stack<Integer> stack = new Stack<>();
stack.add(r);
visited[r] = true;
while (!stack.isEmpty()) {
int a = stack.pop();
System.out.println(a);
for (Integer s : graph.get(a)) {
if (!visited[s]) {
visited[s] = true;
stack.add(s);
}
}
}
}
}출력결과
1
2
4
8
5
3
6
9
7- 위 코드와 스택의 dfs 동작에 대한 추가 설명을 하자면 stack은 FILO(선입후출) 구조이기 때문에, 인접한 노드를 모두 스택에 담은 후에 마지막에 담은 노드 꺼낸 후 그 다음 노드의 인접 노드를 또 다시 모두 스택에 담으면서 탐색을 진행하기 때문에 깊이 우선 탐색이 진행이 된다.
- 그리고 DFS는 재귀로도 구현을 할 수 있는데 코드는 아래와 같다.
private static void dfs(int r) {
visited[r] = true;
System.out.println(r);
for (Integer s : graph.get(r)) {
if (!visited[s]) {
visited[s] = true;
dfs(s);
}
}
}출력결과
1
3
7
6
9
2
5
4
8- 재귀로 구현한 dfs는 위 코드에서 오른쪽부터 탐색을 진행하기 때문에 stack으로 구현한 탐색 결과와 다르지만 결국에는 방향만 달라졌을뿐 깊이 우선 탐색으로 탐색을 진행한다.
너비 우선 탐색
- 시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서,방문했던 정점을 시작으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
- 가까운 정점들을 먼저 방문하고 멀리있는 정점들은 나중에 방문하는 순회방법
- 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야하므로 선입선출의 구조를 갖는 큐를 사용
너비 우선 탐색의 수행순서
(1) 시작 정점 𝑣를 결정하여 방문한다.
(2) 정점 𝑣에 인접한 정점들 중에서 방문하지 않은 정점을 차례로 방문하면서 큐에 enQueue한다.
(3) 방문하지 않은 인접한 정점이 없으면, 방문했던 정점에서 인접한 정점들을 다시 차례로 방문하기 위해서 큐에서 deQueue하여 구한 정점
에서 (2)를 반복한다.
(4) 큐가 공백이 될 때까지 (2)~(3)을 반복한다
깊이 우선 너비 우선순위 코드
private static void bfs(int r) {
Queue<Integer> queue = new LinkedList<>();
queue.add(r);
visited[r] = true;
while (!queue.isEmpty()) {
int a = queue.poll();
System.out.println(a);
for (Integer s : graph.get(a)) {
if (!visited[s]) {
visited[s] = true;
queue.add(s);
}
}
}
}출력결과
1
3
2
7
6
5
4
9
8깊이, 너비 우선 탐색 활용
- 깊이, 너비 우선 탐색의 경우 그래프 탐색의 많이 활용되고 "경로"문제나 시뮬레이션 문제에 자주 나온다.
- 너비 우선 탐색의 경우 최단 거리 구하는 문제로 자주 활용되는데, 아래 백준의 문제 예시로 한번 풀어보자.
문제
N×M크기의 배열로 표현되는 미로가 있다.
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
- 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.
위 문제를 한 줄로 요약하면 (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하는 것이다.
문제 풀이
- 서로 인접한 칸으로만 이동 가능하기 때문에 위 아래 오른쪽 왼쪽 탐색 진행.
- 위 아래 오른쪽 왼쪽을 모두 탐색하면서 방문하지 않은 칸에는 현재 칸의 숫자 + 1을 하면서 탐색을 진행
- 최종적으로 N, M까지 너비 우선 탐색을 하면서 진행하면 N,M에는 최소 칸의 수가 적혀 있음.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
class Node {
int x;
int y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public class baekjoon2178 {
public static int n;
public static int m;
public static int[][] map;
public static boolean[][] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] st = br.readLine().split(" ");
n = Integer.parseInt(st[0]);
m = Integer.parseInt(st[1]);
map = new int[n+1][m+1];
visited = new boolean[n+1][m+1];
for (int i = 1; i <= n; i++) {
String s = br.readLine();
for (int j = 0; j < s.length(); j++) {
map[i][j+1] = Integer.parseInt(String.valueOf(s.charAt(j)));
}
}
bfs();
System.out.println(map[n][m]);
}
public static void bfs() {
int[] dx = {0, 0, 1, -1};
int[] dy = {1, -1, 0, 0};
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(1, 1));
while (!queue.isEmpty()) {
Node node = queue.poll();
int x = node.x;
int y = node.y;
for (int i = 0; i < 4; i++) {
int mx = x + dx[i];
int my = y + dy[i];
if (mx > 0 && my > 0 && mx <= n && my <= m) {
if (!visited[mx][my] && map[mx][my] == 1) {
visited[mx][my] = true;
map[mx][my] = map[x][y] + 1;
queue.add(new Node(mx, my));
}
}
}
}
}
}'Algorithms' 카테고리의 다른 글
| [Algorithms] Dynamic Programming 개념과 구현 (0) | 2020.06.03 |
|---|---|
| [Algorithms] 프린터(프로그래머스 lv2) - queue (0) | 2019.03.08 |
| [Algorithms] 124 나라의 숫자.(프로그래머스 lv1) (1) | 2019.03.04 |
Comments