컴퓨터공학 💻 도서관📚
DFS . 4 본문
DFS 구현 방법 : 1. Stack 으로 구현 , 2. 재귀함수로 구현
DFS (Depth-First-Search) : 깊이 우선 탐색 , 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 , 그래프 탐색
사용한 자료들 : 스택 , visited 배열 , 그래프 (ArrayList 클래스)
DFS 동작 예시: 스택 자료구조인 경우
방문 기준: 번호가 낮은 인접 노드부터
DFS 코드 자바 예제 : 스택 자료구조를 사용한 경우
강의 영상 예시처럼 1 2 7 이렇게 스택에 쌓이는 코드
명 : 명령어
특 : 특수 명령어
자 : 변수 or 자료들
while (명) + isEmpty() 메서드 (특)
if (명) + visited[ ] 배열 (자) - - > 방문처리 ( 방문했으면 넘어가고 , 안 했으면 할 일 하고 )
for (명) + graph 리스트 (자) + get 메서드 (특) - - > graph 리스트 순회
if (명) + visited[ ] 배열 (자) - - > 방문처리 ( 방문했으면 넘아가고, 안 했으면 할 일 하고 )
break (명)
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 + 스택이 빌 때까지 ( isEmpty() 메서드 )
(방문처리)
// 스택에서 peek 하기
// peek 한거 방문 처리
// boolean 이웃있다 변수 선언
( graph 리스트 순회 )
// for( int neighbor : graph.get(current) ) peek 노드의 인접 노드 순회
// if 방문 안 했으면 스택에 추가하고 이웃있다 변수 true로 바꾸고 break;
// 이웃있다 변수가 false 면 스택에서 pop 하기
간선 연결 부가 설명
graph.get(1).addAll(Arrays.asList(2, 3, 8)); 이 한줄에 대한 부가설명
graph.get(1).addAll(Arrays.asList(2, 3, 8)); 이 한줄에 대한 부가설명
asList 메서드에 대한 부가 설명
computer-science-library.tistory.com
코드 구조
main 메서드
그래프 선언
그래프 초기화
그래프 정렬
방문 배열 선언
방문 순서 배열 선언
for --> 방문 안 했으면 DFS 메서드 호출
DFS 메서드
스택 선언
스택 초기화
while --> 스택이 빌 때까지(가장 깊은 부분까지 탐색이 끝날 때까지) (isEmpty 메서드)
peek로 top 요소(current) 꺼내기 --> 방문 여부 확인 --> 방문했으면 방문 순서 배열에 추가
논리 연산자 선언 --> 향상된 for --> graph.get(current)로 인접 노드 방문 여부 확인 --> 방문x면 push
논리 연산자 false면 더 이상 갈 곳이 없으므로 pop 하기
import java.util.*;
public class DFSVisitAllPeek {
public static void main(String[] args) { // 이건 main 메서드
int n = 8;
// 그래프 선언
List<List<Integer>> graph = new ArrayList<>();// 2차원 객체 배열 (방만 생겨서 직접 넣어줘야 함)
for (int i = 0; i <= n; i++) { // detail : n 까지 포함하기 ( i <= n )
graph.add(new ArrayList<>()); // 객체 배열의 각 요소가 독립적인 객체가 되어야 하기 때문에 각각의 것을 직접 넣어줌
}
// 그래프 초기화(간선 연결)
graph.get(1).addAll(Arrays.asList(2, 3, 8)); // addAll, Arrays, asList
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); // 특수 명령어(Collections 클래스)
}
boolean[] visited = new boolean[n + 1]; // 방문 배열 선언
List<Integer> visitOrder = new ArrayList<>(); // 방문 순서 배열
// 전체 노드 다 방문하도록 루프
for (int i = 1; i <= n; i++) {
if (!visited[i]) { // (visited[i] == 0) 이건 안돼! 자료형 불일치 거든 (boolean != int)
dfsPeek(graph, visited, i, visitOrder); //main 메서드에서 dfsPeek 메서드 호출
}
}
// 방문 순서 출력
System.out.println("방문 순서: " + visitOrder);
}
// 여기부터가 스택을 활용한 DFS 구현
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;
// 자료와 기본 명령어의 조합 : visited 배열 + 향상된 for문 + if문
for (int neighbor : graph.get(current)) { // visited 배열 + 향상된 for문으로 순회
if (!visited[neighbor]) {
stack.push(neighbor); // 방문 안 한 인접 노드 하나만 push
hasUnvisitedNeighbor = true;
break;
}
}
if (!hasUnvisitedNeighbor) {
stack.pop(); // 더 이상 갈 곳이 없으면 pop
}
}
}
}
import java.util.*;
public class DFSVisitAllPeek {
// main메서드가 static 메서드이기 때문에 멤버변수들도 static으로 선언해야 한다.
public static int n = 8; // static 상수 선언
public static List<List<Integer>> graph = new ArrayList<>();
public static boolean[] visited = new boolean[n + 1];
public static List<Integer> visitOrder = new ArrayList<>();
public static void main(String[] args) {
// 그래프 초기화
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);
}
// 모든 노드 방문
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
dfsPeek(i);
}
}
System.out.println("방문 순서: " + visitOrder);
}
public static void dfsPeek(int start) {
Stack<Integer> stack = new Stack<>();
stack.push(start);
while (!stack.isEmpty()) {
int current = stack.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);
hasUnvisitedNeighbor = true;
break;
}
}
if (!hasUnvisitedNeighbor) {
stack.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 |
