[알고리즘] DFS

🚀DFS에 대해 잘 정리해둔 블로그가 있어 링크 걸어둠
https://freestrokes.tistory.com/88
​

👀DFS/BFS 적용 판단시 참고

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용
DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

1) 그래프의 모든 정점을 방문하는 것이 주요한 문제
단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.

둘 중 편한 것을 사용하시면 됩니다.
​

2) 경로의 특징을 저장해둬야 하는 문제

예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)

​

3) 최단거리 구해야 하는 문제

미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.

왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

출처: https://devuna.tistory.com/32 [튜나 개발일기]
​
​

👩‍💻 DFS구현 - 인접행렬

class dfsGraph{
    private static int nV;
    private int[][] dfsGraph;
    private boolean[] visited;
    
    public dfsGraph(int nV){
        this.nV = nV;
        this.dfsGraph = new int[nV+1][nV+1];
        this.visited = new boolean[nV+1];
    }
    
    public int[][] get(){
        return this.dfsGraph;
    }
    
    public void put(int x, int y){
        this.dfsGraph[x][y] = this.dfsGraph[y][x] = 1;
    }
    
    public void putSingle(int x, int y){
        this.dfsGraph[x][y] = 1;
    }
    
    public void printGraph(){
        for(int i=0; i<this.nV+1; i++){
            for(int j=0; j<this.nV+1; j++){
                System.out.print(this.dfsGraph[i][j] + " ");
            }
            System.out.println("");
        }
    }
    
    public void dfs(int x){
        
        if(visited[x]) return;
        
        this.visited[x] = true;
        System.out.print(x + "-");
        
        for(int i=0; i<dfsGraph.length; i++){
            if(dfsGraph[x][i]==1 && !visited[i]){
                dfs(i);
            }
        }
        
    }
    
    
}


class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int nV = 8;
        
        dfsGraph dfsGraph = new dfsGraph(nV);
        
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        dfsGraph.printGraph();
        dfsGraph.dfs(1);
        
        
        return answer;
    }
}

👩‍💻 DFS구현 - 인접리스트 : 재귀

import java.util.ArrayList;

class DfsGraph{
    private static int nV;
    private boolean[] visited;
    private ArrayList<ArrayList<Integer>> dfsGraph;
    
    public DfsGraph(int nV){
        this.nV = nV;
        this.visited = new boolean[nV+1];
        this.dfsGraph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0; i<nV+1; i++){
            this.dfsGraph.add(new ArrayList<Integer>());
        }
    }
    
    public ArrayList<ArrayList<Integer>> getGraph(){
        return this.dfsGraph;
    }
    
    public void put(int x, int y){
        this.dfsGraph.get(x).add(y);
        this.dfsGraph.get(y).add(x);
    }
    
    public void putSingle(int x, int y){
        this.dfsGraph.get(x).add(y);
    }
    
    public void print(){
        for(int i=0; i<this.dfsGraph.size(); i++){
            System.out.print( i + "의 인접리스트 : ");
            for(int j=0; j<this.dfsGraph.get(i).size(); j++){
                System.out.print(" -> " + this.dfsGraph.get(i).get(j));
            }
            System.out.println(" ");
        }
    }
    
    public void dfs(int x){
        if(this.visited[x]) return;
        this.visited[x] = true;
        
        System.out.print(x + "-");
        
        for(int i : this.dfsGraph.get(x)){
            if(!this.visited[i]){
                dfs(i);
            }
        }
    }
    
}

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int nV = 8;
        
        DfsGraph dfsGraph = new DfsGraph(nV);
        
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        dfsGraph.print();
        
        dfsGraph.dfs(1);

        
        return answer;
    }
}

DFS구현 - 인접리스트 : 스택

import java.util.ArrayList;
import java.util.Stack;

class DfsGraph{
    private static int nV;
    private ArrayList<ArrayList<Integer>> dfsGraph;
    private boolean[] visited;
    
    public DfsGraph(int nV){
        this.nV = nV;
        this.dfsGraph = new ArrayList<ArrayList<Integer>>();
        this.visited = new boolean[nV+1];
        
        for(int i=0; i<nV+1; i++){
            this.dfsGraph.add(new ArrayList<Integer>());
        }
    }
    
    public ArrayList<ArrayList<Integer>> get(){
        return this.dfsGraph;
    }
    
    public void put(int x, int y){
        this.dfsGraph.get(x).add(y);
        this.dfsGraph.get(y).add(x);
    }
    
    public void putSingle(int x, int y){
        this.dfsGraph.get(x).add(y);
    }
    
    public void print(){
        for(int i=0; i<this.dfsGraph.size(); i++){
            for(int j=0; j<this.dfsGraph.get(i).size(); j++){
                System.out.print(this.dfsGraph.get(i).get(j) + " ->");
            }
            System.out.println();
        }
    }
    
    public void dfs(int x){
        Stack<Integer> st = new Stack<>();
        st.push(x);
        visited[x] = true;
        
        while(!st.isEmpty()){
            int t = st.pop();
            System.out.print(t);
            for(int i : this.dfsGraph.get(t)){
                if(!visited[i]){
                    st.push(i);
                    visited[i] = true;
                }
            }
        }
        
    }
}

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        int nV = 8;
        
        DfsGraph dfsGraph = new DfsGraph(nV);
        
        dfsGraph.put(1, 2);
        dfsGraph.put(1, 3);
        dfsGraph.put(2, 4);
        dfsGraph.put(2, 5);
        dfsGraph.put(3, 6);
        dfsGraph.put(3, 7);
        dfsGraph.put(4, 8);
        dfsGraph.put(5, 8);
        dfsGraph.put(6, 8);
        dfsGraph.put(7, 8);
        
        dfsGraph.print();
        
        dfsGraph.dfs(1);
        
        return answer;
    }
}