드디어 3일만에 내 속을 썩이던 DFS 푸는 기초적인 방법을 이해한 것 같다 ㅠㅠ
계속 하다보면 익숙해 지겠지?
문제(가정)
1) 노드와 간선은 5,6이고
2) 노드의 관계는 두번째 줄이다.
3) 무방향 연결 그래프다.
재귀함수
public class Main {
static final int MAX_N = 10;
static int N,E;
static int[][] graph = new int [MAX_N][MAX_N]; // 인접행렬
static boolean[] visited = new boolean[MAX_N];
public static void main(String[] args) {
// 5 6
// 0 1, 0 2, 1 3, 1 4, 2 4, 3 4
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
E = sc.nextInt();
for (int i=0; i < E; ++i) {
int u = sc.nextInt();
int v = sc.nextInt();
graph[u][v] = graph[v][u] = 1;
}
dfs(0);
}
static void dfs(int node) { // 매개변수는 시작노드다.
visited[node] = true; // 방문한 노드를 true로 설정
System.out.print(node + " ");
//
for (int next=0; next < N; ++next) {
if (!visited[next] && graph[node][next] != 0) {
dfs[next];
}
}
}
}
차근차근 살펴보자.
1)
for (int i=0; i < E; ++i) {
int u = sc.nextInt();
int v = sc.nextInt();
graph[u][v] = graph[v][u] = 1;
} 연결된 노드 두 개를 각각 u,v에 담는다.
그다음 무방향 연결 그래프이기 때문에 인접행렬에 graph[u][v] = graph[v][u] = 1;로 표시한다.
cf. 만약 방향 그래프에서 정점 u에서 v로 연결된 경우에는
graph[u][v] = 1; 로 작성하면 된다.
2)
static void dfs(int node) { // 매개변수는 시작노드다.
visited[node] = true; // 방문한 노드를 true로 설정
System.out.print(node + " ");
//
for (int next=0; next < N; ++next) { // next++와 동일
if (!visited[next] && graph[node][next] != 0) {
dfs[next];
}
}
}dfs(시작노드)를 실행하면 시작노드를 visited[]에 true로 설정한다.
출력값은 "0" 이다.
for문으로 N번(노드의 개수) 반복하는데, 방문하지 않은 노드 중에서, 현재 노드와 연결되어 있는 노드들 중 첫번째 노드로 이동한다.
ex) 0번 노드는 1,2 둘 다 갈 수 있지만 1이 먼저 등장하므로 1로 이동한다.
(단, 스택을 사용하면 이 때의 순서는 달라진다.)
이러한 작업이 N만큼 반복하면 끝이 나며, 반복문이 종료되었을 때 최종 출력 값은
"0 1 3 4 2"다.
🤷♀️ 근데 가장 깊은 노드인 3을 방문하고 나서 어떻게 다시 0으로 올라간 다음, 2로 이동할 수 있는걸까? (중요)
🔑 "콜 스택" 때문이다.
재귀함수의 경우, 종료 조건을 만날 때까지 차례대로 스택을 쌓다가 종료 조건을 만나면 다시 돌아가며 계산을 하며 마지막에 결과값을 반환한다.
마찬가지로 dfs() 또한 동일하게 작동한다.
따라서 아래와 같이 작동한다.
방문: 0
방문: 1
방문: 3
방문: 4
돌아가기: 4 -> 3
돌아가기: 3 -> 1
돌아가기: 1 -> 0
방문: 2
돌아가기: 2 -> 0
따라서 최종 출력값은 "0 1 3 4 2"다.
스택
public class Main {
static final int MAX_N = 10;
static int N,E;
static int[][] graph = new int [MAX_N][MAX_N];
public static void main(String[] args) {
// 5 6
// 0 1, 0 2, 1 3, 1 4, 2 4, 3 4
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
E = sc.nextInt();
for (int i=0; i < E; ++i) {
int u = sc.nextInt();
int v = sc.nextInt();
graph[u][v] = graph[v][u] = 1;
}
dfs(0);
}
static void dfs(int node) {
boolean[] visited = new boolean[MAX_N];
Stack<Integer> mystack = new Stack<>();
mystack.push(node);
while(!mystack.empty()) {
int curr = mystack.pop();
if (visited[curr]) {
continue;
}
visited[curr]= true;
System.out.println(curr + " ");
// 특정 노드에 대한 다른 노드를 비교
for(int next =0; next < N; ++next) {
if (!visited[next] && graph[curr][next] != 0) {
mystack.push(next);
}
}
}
}
}-
스택은 재귀함수를 사용할 때와 실행결과가 다르다.
실행 방식은 재귀함수와 거의 유사하므로 생략하겠다. -
현재 노드와 인접한 노드 중 아직 방문하지 않은 노드를 스택에 푸시한다.
-
스택의 맨 윗부분은 현재 탐색의 '전선(frontier)'을 나타내며, 다음 탐색 대상이 될 노드를 가리킨다.
-
단, 모든 노드가 visited[]가 true로 표시(별표 친 부분)되어, continue로 인해 while문으로 되돌아 가는 부분을 조심하자. 원래 stack에 [1,1]이 있었지만 두 번 연속 pop()되어 반복문이 종료된다.
-
근데 보통 순서보장 및 가독성 때문에 재귀함수를 사용한다고 한다. 단, 스택오버플로우는 조심해야 한다.
반복문 잡지식
for(int next =0; next < N; ++next) {
if (!visited[next] && graph[curr][next] != 0) {
mystack.push(next);
}
}next가 0일 때, ++next는 전위 증가 이기 때문에 next가 1부터 시작한다고 착각했다.
그래서 next++와 ++next는 각각 0,1로 다른 줄 알았는데 아니였다.
for (초기화; 조건; 증감) {
// 반복할 코드
}루프의 증감 부분에서 next++와 ++next 사이에는 기능적 차이가 없다.
왜냐하면, 둘 다 next의 값을 1만큼 증가시키지만, 이 증가 연산이 적용되는 시점은 반복의 끝이기 때문이다. 즉, 반복문의 증감이 이루어지는 시점은 언제나 동일하기 때문이다.
따라서 루프의 각 반복에서 next의 값을 사용하는 코드에는 영향을 주지 않는다.
참고
