DFS 공부

★DFS (깊이 우선 탐색) : 한 우물만 파고 끝까지 내려가는 탐색. 스택(Stack)의 원리나 재귀함수 사용

★BFS (너비 우선 탐색) : 내 주변부터 가까운 곳을 넓게 퍼져나가며 탐색. 큐(Queue)의 자료구조 사용. 최단거리는 무조건 BFS

 

대표 유형 : 경로탐색, 네트워크, 조합 만들기

 

DFS : 재귀함수

BFS : Queue / LinkedList

 

★ 재귀 함수의 필수 2대 조건★

1. 기저 조건(Base Case) : "언제 멈출 것인가?" 를 정하는 탈출 조건 (if 문으로 구현)

2. 재귀 단계 (Recursive Case) : 문제를 더 작은 단위로 쪼개서 자기 자신을 다시 호출

 

<그래프를 코드로 표현하는 방법>

1. 인접 행렬

노드가 총 3개 있고, 1-2, 1-3 연결된 그래프 (인덱스를 번호와 맞추기 위해 크기를 N+1로 잡는게 팁)

int[][] graph = new int[4][4]; // 0번은 안쓰고 1~3번 노드 사용

graph[1][2] = 1; graph[2][1] = 1; // 1번과 2번이 연결됨(양방향)
graph[1][3] = 1; graph[3][1] = 1; // 1번과 3번이 연결됨

장점 : graph[1][3] = 1 인지만 확인하면 되니까 빛의 속도로 확인 가능

단점 : 노드가 1만개인데 연결된 선은 고작 2개라면, 메모리를 엄청나게 낭비

 

2. 인접 리스트 ★실전 빈출

각 노드마다 바구니(ArrayList) 를 하나씩 주고, 연결된 이웃 번호를 담아두는 방법

- 1번 바구니 : [2,3] (2,3번과 연결)

- 2번 바구니 : [1] (1번과 연결)

import java.util.ArrayList;

// 노드 개수만큼 ArrayList 공간(바구니 배열)을 만든다
ArrayList<Integer>[] graph = new ArrayList[4];

// 각 방마다 진자 바구니를 채워 초기화한다
for(int i=1; i<=3; i++){
	graph[i] = new ArrayList<>();
}

// 연결 정보 입력하기
graph[1].add(2); graph[2].add(1); // 1번 바구니에 2 넣고, 2번 바구니에 1 넣기
graph[1].add(3); graph[3].add(10; // 1번 바구니에 3 넣고, 3번 바구니에 1 넣기

장점 : 연결된 만큼만 숫자를 저장해서 메모리를 효율적으로 사용

단점 : 코드 모양이 복잡해보인다

 

★실전에서 뭘 써야할까?

1. 바둑판, 미로찾기, 모눈종이 맵 : 고민도 하지말고 1번 인접행렬(2차원 배열)

2. 트리구조, 컴퓨터 네트워크, 친구 관계 맵 : 2번 인접리스트

 

DFS의 실전 뼈대 코드와 방문(visited) 체크 개념

 

★DFS 실전 뼈대 코드 ★

import java.util.ArrayList;

class Solution{
	// 전역 변수로 그래프 도화지와 방문체크 배열 선언
    static ArrayList<Integer>[] graph;
    static boolean[] visited;
    
    public void dfs(int node){
    	// [체크인] 현재 노드에 방문 도장을 찍는다
        visited[node] = true;
        System.out.print(node + "->");
        
        // [이웃 탐색] 현재 노드와 연결된 친구(이웃)들을 한놈씩 꺼낸다
        for(int nextNode : graph[node]){
        	// [방어 조건] 만약 방문한적이 없다면?
            if(!visited[nextNode]){
            	dfs(nextNode);
            }
        }
    }
}