컴퓨터공학 💻 도서관📚
DFS . 4 본문


DFS 동작 예시: 스택 자료구조인 경우
방문 기준: 번호가 낮은 인접 노드부터


DFS 코드 자바 예제 : 스택 자료구조를 사용한 경우
강의 영상 예시처럼 1 2 7 이렇게 스택에 쌓이는 코드
public class DFSVisitAllPeek {
public static void main(String[] args) {
// 배열 선언
// 객체 배열 요소 추가
// 그래프 만들기 (간선 연결)
// 인접 노드들 숫자순으로 정렬 (안전장치)
( boolean[] visited = new boolean[n + 1]; 배열선언 n+1 )
// for + dfs 함수를 이용하여 모든 노드 방문하기
public static void dfsPeek( ~~ ){
// 스택 선언
// 스택에 시작노드 push 하기
// while + 스택이 빌 때까지
// 스택에서 peek 하기
// peek 한거 방문 처리
// boolean 이웃있다 변수 선언
// for(int neighbor : graph.get(current)) peek 노드의 인접 노드 순회
// 방문 안 했으면 스택에 추가하고 이웃있다 변수 true로 바꾸고 break;
// 이웃있다 변수가 false 면 스택에서 pop 하기
import java.util.*;
public class DFSVisitAllPeek {
public static void main(String[] args) {
int n = 8;
// 그래프 초기화
List<List<Integer>> graph = new ArrayList<>(); // 객체 배열 (방만 생겨서 직접 넣어줘야 함)
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>()); // 객체 배열의 각 요소가 독립적인 객체가 되어야 하기 때문에 각각의 것을 직접 넣어줌
}
// 간선 연결
graph.get(1).addAll(Arrays.asList(2, 3, 8));
graph.get(2).addAll(Arrays.asList(1, 7));
graph.get(3).addAll(Arrays.asList(1, 4, 5));
graph.get(4).addAll(Arrays.asList(3, 5));
graph.get(5).addAll(Arrays.asList(3, 4));
graph.get(6).addAll(Arrays.asList(7));
graph.get(7).addAll(Arrays.asList(2, 6, 8));
graph.get(8).addAll(Arrays.asList(1, 7));
// 인접 노드를 숫자순으로 정렬 // 일반적인 상황을 대비한 안전장치
for (List<Integer> neighbors : graph) {
Collections.sort(neighbors);
}
boolean[] visited = new boolean[n + 1];
List<Integer> visitOrder = new ArrayList<>();
// 전체 노드 다 방문하도록 루프
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfsPeek(graph, visited, i, visitOrder);
}
}
// 방문 순서 출력
System.out.println("방문 순서: " + visitOrder);
}
public static void dfsPeek(List<List<Integer>> graph, boolean[] visited, int start, List<Integer> visitOrder) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.peek(); // peek으로 현재 노드를 확인
if (!visited[current]) {
visited[current] = true;
visitOrder.add(current);
}
boolean hasUnvisitedNeighbor = false;
for (int neighbor : graph.get(current)) {
if (!visited[neighbor]) {
stack.push(neighbor); // 방문 안 한 인접 노드 하나만 push
hasUnvisitedNeighbor = true;
break;
}
}
if (!hasUnvisitedNeighbor) {
stack.pop(); // 더 이상 갈 곳이 없으면 pop
}
}
}
}
강의 영상과는 조금 다르게 (1) 8 3 (2) 8 7 이렇게 쌓이는 경우
import java.util.*;
public class DFSExample {
public static void main(String[] args) { // main 함수 : 그래프 세팅함
// 노드 개수
int n = 8;
// 인접 리스트 생성 (1-based index)
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 그래프 간선 추가
graph.get(1).addAll(Arrays.asList(2, 3, 8));
graph.get(2).addAll(Arrays.asList(1, 7));
graph.get(3).addAll(Arrays.asList(1, 4, 5));
graph.get(4).addAll(Arrays.asList(3, 5));
graph.get(5).addAll(Arrays.asList(3, 4));
graph.get(6).addAll(Arrays.asList(7));
graph.get(7).addAll(Arrays.asList(2, 6, 8));
graph.get(8).addAll(Arrays.asList(1, 7));
// 작은 숫자부터 방문하기 위해 정렬 // 일반적인 상황을 대비한 안전장치
for (List<Integer> neighbors : graph) {
Collections.sort(neighbors);
}
boolean[] visited = new boolean[n + 1];
dfsStack(graph, visited, 1); // 1번 노드부터 시작
}
public static void dfsStack(List<List<Integer>> graph, boolean[] visited, int start) {
Stack<Integer> stack = new Stack<>(); // stack 자료구조
stack.push(start);
while (!stack.isEmpty()) {
int node = stack.pop();
if (!visited[node]) {
visited[node] = true;
System.out.print(node + " ");
// 인접 노드를 역순으로 스택에 넣어야 작은 숫자부터 먼저 꺼내짐
List<Integer> neighbors = graph.get(node);
for (int i = neighbors.size() - 1; i >= 0; i--) {
int next = neighbors.get(i);
if (!visited[next]) {
stack.push(next);
}
}
}
}
}
}



DFS 코드 예제 : 재귀함수를 사용한 경우
(재귀함수로 구현하고 노드 방문 순서를 출력한 예시)

일반적으로 그래프 문제에서는 노드의 번호가 1번부터 시작하기 때문에
그래프를 초기화할 때 인덱스 0에 대한 내용은 비워두고 1번 인덱스부터 채운다
그렇기에 방문여부를 확인하는 리스트의 요소 개수를 노드 개수보다 1 높은 수로 선언하기
2차원 리스트를 선언할 때 숫자들을 작은 수부터 차례대로 써서
재귀함수를 통해 우리가 원하는 대로 출력이 되게 만들 수 있었다.

자바
ArrayList 는 특정 인덱스에 접근하기 위해 상수시간이 소요되기 때문에 일반 배열보다 더 좋다
ArrayList를 중첩된 형태로 이용해서 그래프를 표현할 수 있다

import java.util.*;
public class Main {
public static boolean[] visited = new boolean[9];
public static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
// DFS 함수 정의
public static void dfs(int x) {
// 현재 노드를 방문 처리
visited[x] = true;
System.out.print(x + " ");
// 현재 노드와 연결된 다른 노드를 재귀적으로 방문
for (int i = 0; i < graph.get(x).size(); i++) {
int y = graph.get(x).get(i);
if (!visited[y]) dfs(y);
}
}
public static void main(String[] args) {
// 그래프 초기화
for (int i = 0; i < 9; i++) {
graph.add(new ArrayList<Integer>());
}
// 노드 1에 연결된 노드 정보 저장
graph.get(1).add(2);
graph.get(1).add(3);
graph.get(1).add(8);
// 노드 2에 연결된 노드 정보 저장
graph.get(2).add(1);
graph.get(2).add(7);
// 노드 3에 연결된 노드 정보 저장
graph.get(3).add(1);
graph.get(3).add(4);
graph.get(3).add(5);
// 노드 4에 연결된 노드 정보 저장
graph.get(4).add(3);
graph.get(4).add(5);
// 노드 5에 연결된 노드 정보 저장
graph.get(5).add(3);
graph.get(5).add(4);
// 노드 6에 연결된 노드 정보 저장
graph.get(6).add(7);
// 노드 7에 연결된 노드 정보 저장
graph.get(7).add(2);
graph.get(7).add(6);
graph.get(7).add(8);
// 노드 8에 연결된 노드 정보 저장
graph.get(8).add(1);
graph.get(8).add(7);
dfs(1);
}
}
'✅🌲강의 복습 노트 > 이코테2021 알고리즘 훈련' 카테고리의 다른 글
DFS&BFS 유형 문제 . 6 (2) | 2024.11.04 |
---|---|
BFS . 5 (0) | 2024.11.03 |
재귀함수 . 3 (0) | 2024.10.28 |
큐 . 2 (0) | 2024.10.27 |
스택 . 1 (0) | 2024.10.27 |