이전에 dfs 알고리즘과 bfs 알고리즘에 대해 한 번 살펴본 적이 있었습니다.
시간이 오래 지나 흐릿해진 기억을 되짚어보기 위해 정리해봅니다.
BFS, DFS 두가지 모두 그래프를 탐색하는 방법입니다.
그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며,
그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다.
dfs 알고리즘의 진행 단계는 아래와 같습니다.
위 예시와 같이 dfs 알고리즘으로 문제를 해결한다고 가정해봅시다.
1번 노드에서 시작을 한다면
1 -> 2 -> 3
1 -> 5 -> 6
1 -> 5 -> 8
1 -> 9 -> 10
순서로 노드를 이동할 수 있습니다.
특정 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이 bfs 방법이었다고 한다면
dfs 방법은 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다.
앞에서 배웠던 내용을 복기해 봅시다.
bfs는 특정 노드에서 최단 거리를 구할 때 많이 사용하는 알고리즘입니다.
그렇다면 dfs는 어떨때 사용을 할까요??
dfs는 각각의 분기의 시작점부터 끝까지 끊어지지 않고 한번에 쭈욱 이동하기 때문에 이러한 특성을 살려 '이동 경로'에 관한 알고리즘을 풀 때 많이 사용합니다.
bfs가 queue를 이용하여 문제를 해결하였다면
dfs는 stack을 이용하여 문제를 해결할 수 있습니다.
https://programmers.co.kr/learn/courses/30/lessons/43164
프로그래머스에서 제공하고 있는 dfs 문제를 한번 풀어보았습니다.
티켓을 주고, 방문하는 공항 경로를 배열에 담아 return 하는 문제입니다.
단 방문할 수 있는 경로가 2가지 이상일 경우에는 알파벳 순서가 앞서는 경로를 return 하라고 했습니다.
dfs에서 핵심이 되는 코드는 아래에서 확인할 수 있습니다.
stack과 재귀함수를 이용하여 구현을 하였는데
사용한 ticket은 visit라는 배열에 저장을 해놓고 재 방문을 하지 않도록 방지합니다.
그리고 방문할 공항을 stack에 집어놓고 재귀함수를 다시 호출합니다.
for (int i = 0; i < tickets.length; i++) {
// 티켓을 사용하지 않았고, 티켓에 현재 스타트 지점이 있을 경우
if (!visit[i] && tickets[i][0].equals(currentAirport)) {
String nextAirport = tickets[i][1];
visit[i] = true;
stack.add(nextAirport);
dfs43164(count + 1, stack, tickets);
stack.pop();
visit[i] = false;
}
}bfs던 dfs던 종료시점을 지정해주는 것이 중요합니다.
종료하는 시점은 모든 ticket을 사용하였을 경우입니다.
if (count == tickets.length) {
result.add(String.join(" ", stack));
return;
}
전체 코드는 아래에서 확인할 수 있습니다.
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class p43164_2 {
private static boolean[] visit;
private static List<String> result = new ArrayList<>();
public static void main(String[] args) {
String[][] tickets = {{"ICN", "JFK"}, {"HND", "IAD"}, {"JFK", "HND"}};
visit = new boolean[tickets.length];
Stack<String> stack = new Stack<>();
stack.add("ICN");
// index, 사용한 티켓의 수, stack
dfs43164(0, stack, tickets);
Collections.sort(result);
System.out.println(result.get(0));
}
private static void dfs43164(int count, Stack<String> stack, String[][] tickets) {
String currentAirport = stack.peek();
if (count == tickets.length) {
result.add(String.join(" ", stack));
return;
}
for (int i = 0; i < tickets.length; i++) {
// 티켓을 사용하지 않았고, 티켓에 현재 스타트 지점이 있을 경우
if (!visit[i] && tickets[i][0].equals(currentAirport)) {
String nextAirport = tickets[i][1];
visit[i] = true;
stack.add(nextAirport);
dfs43164(count + 1, stack, tickets);
stack.pop();
visit[i] = false;
}
}
}
}