import java.util.*;
class Solution {
int n = 5;
/**
* 스택 구조이므로 DFS의 반대 순서로 동작한다. (간선에 방향이 없어야하며, 동일하게 연결되어야한다.)
* @param n - 노드의 수
* @param graph - 노드간의 간선이 표현된 그래프
*/
@Test
public void solution() {
int[][] graph = new int[n][6];
graph[0][1] = graph[1][0]= 1;
graph[0][2] = graph[2][0] = 1;
graph[1][3] = graph[3][1] = 1;
graph[1][4] = graph[4][1] = 1;
graph[2][4] = graph[4][2] = 1;
graph[3][4] = graph[4][3] = 1;
dfs(0, graph);
}
public void dfs(int startNode, int[][] graph) {
boolean[] visited = new boolean[n];
Stack<Integer> stack = new Stack<>();
stack.push(startNode);
while(stack.empty() == false) {
int currentNode = stack.pop();
if(visited[currentNode]) {
continue;
}
visited[currentNode] = true;
System.out.println(currentNode + "방문");
for(int next = 0; next < n; next++) {
if(visited[next] == false && graph[currentNode][next] != 0) {
stack.push(next);
}
}
}
}
}
결과
0방문
2방문
4방문
3방문
1방문