dfs와 bfs

 

 

 

dfs는 재귀함수를 이용해서 구현한다.

 

관계식이 명확하게 보이기 때문인데.. 

 

 

 

 

위와 같은 그래프를 dfs로 탐색한다고 하면, 노드 A에서 갈 수 있는 노드 = A + B에서가는거 + C에서가는거

 

이렇게 관계식이 나온다.

 

그래프를 탐색하는 함수를 하나 만들어놓고 ~에서 갈 수 있는 노드를 탐색할 때 그 함수를 계속해서 호출하면 되기에 재귀함수를 통해 직관적으로 구현할 수 있다.

 

재귀함수를 통해 깊게 깊게 파고들어서 depth first search라고 불린다.

 

 

탐색을 진행할 때는 탐색한 곳을 다시 탐색하는 경우를 피하기 위해 visit배열을 그래프와 함께 사용한다.

 

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;    
    static boolean[] visit;    

    static ArrayList<Integer>[] list;

    static int cnt;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList[N + 1];
        visit = new boolean[N+1];

        for(int i=0; i<N+1; i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            list[start].add(end);
            list[end].add(start);
        }      
        
        
        dfs(1);

      
        System.out.println(cnt == 0 ? cnt : cnt-1);
        
        
    }

    static void dfs(int v){

        for(int i=0; i<list[v].size(); i++){
            int curV = list[v].get(i);
            if(!visit[curV]){
                cnt++;
                visit[curV] = true;
                dfs(curV);
            }
        }
    }
}

 

 

리스트를 사용해 그래프를 구현했을 때 dfs를 구현한 예시이다. (PS시 항상 극단적인 테스트케이스를 고려하자)

 

 

 

격자에서 탐색을 진행할 때도 dfs를 사용할 수 있다.

 

격자 자체를 그래프 자료구조로 보고 탐색할 수 있어 따로 리스트나 행렬을 만들지 않아도 되고, 격자 탐색 테크닉인 dr dc배열을 선언 해 놓고 문제에 적용해 dfs를 돌릴 수 있다.

 

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;    
    static int[][] map;
    static boolean[][] visit;

    static int[] dr = {1,0};
    static int[] dc = {0,1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visit = new boolean[N][M];

        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0,0);

        
        if(visit[N-1][M-1]){
            System.out.println(1);
        }else{
            System.out.println(0);
        }  
        

                
    }

    static void dfs(int r, int c){

        visit[r][c] = true;
        
        for(int i=0; i<2; i++){
            int nextR = r + dr[i];
            int nextC = c + dc[i];
            
            if(nextR >= N || nextR <= -1 || nextC >= M || nextC <= -1){
                continue;
            }

            if(map[nextR][nextC] == 0){
                continue;
            }

            if(visit[nextR][nextC]){
                continue;
            }

            dfs(nextR, nextC);

            
        }


    }
}

 

 

dfs는 재귀함수로 구현되어있고, visit배열을 통해 방문했던 곳을 재방문하는 일이 없도록 한다... 이 두 가지가 dfs의 핵심이라고 할 수 있다.

 

 

 

 

bfs도 dfs와 마찬가지로 그래프를 탐색할 때 사용되는 알고리즘이다.

 

dfs는 재귀함수로 구현하고, bfs는 큐를 이용해서 구현한다.

 

같은 그래프 탐색인데 뭐가 다르냐? 라고 하면... dfs는 재귀함수로 구현돼있어 백트래킹을 사용하기 좋고, bfs는 최단 거리를 계산할 때 dfs보다는 쉽다. (가중치가 없는 경우만. 가중치가 있는 경우는 다익스트라 등 다른 알고리즘을 사용하자.)

 

이 외에도 다른 차이점들이 있을 것 같은데.. 아직까지는 잘 모르겠다.

 

dfs에서는 노드를 깊게깊게 파고들며 탐색하는 방법을 채택하고, bfs는 한 노드에 연결된 다른 노드들을 탐색하는 방식으로 진행돼, 최단 거리를 계산하기 좋다.

 

 

    import java.io.*;
    import java.util.*;

    public class Main {
        static int N, K;    
        static int[][] map;
        static boolean[][] visit;

        static int[] dr = {-1,1,0,0};
        static int[] dc = {0,0,-1,1};

        static int cnt = 0;

        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            map = new int[N][N];
            visit = new boolean[N][N];

            for(int i=0; i<N; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<N; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }    


            Queue<Point> q = new LinkedList<>();    


            for(int i=0; i<K; i++){
                st = new StringTokenizer(br.readLine());
                int r = Integer.parseInt(st.nextToken()) - 1;
                int c = Integer.parseInt(st.nextToken()) - 1;
                q.add(new Point(r,c));
                visit[r][c] = true;
                cnt++;
            }


            while(!q.isEmpty()){
                Point cur = q.poll();
                

                for(int i=0; i<4; i++){
                    int nextR = cur.r + dr[i];
                    int nextC = cur.c + dc[i];

                    if(nextR >= N || nextR <= -1 || nextC >= N || nextC <= -1 || map[nextR][nextC] == 1){
                        continue;
                    }

                    if(visit[nextR][nextC]){
                        continue;
                    }


                    visit[nextR][nextC] = true;
                    q.add(new Point(nextR, nextC));
                    cnt++;
                }

                
            }

            System.out.println(cnt);
        
            

        }
    }

    class Point{
        int r,c;
        Point(int r, int c){
            this.r =r;
            this.c = c;
        }
    }

 

 

bfs를 사용해 격자를 탐색하는 예시이다.

 

 

 

    import java.io.*;
    import java.util.*;

    public class Main {
        static int N, K;    
        static int[][] map;
        static int[][] dist;

        static int[] dr = {-1,1,0,0};
        static int[] dc = {0,0,-1,1};

        static int cnt = 0;

        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            
            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            map = new int[N][K];
            dist = new int[N][K];
                        

            for(int i=0; i<N; i++){
                st = new StringTokenizer(br.readLine());
                for(int j=0; j<K; j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }    

            dist[0][0] = 1;


            Queue<Point> q = new LinkedList<>();   

            q.add(new Point(0,0));

            while(!q.isEmpty()){
                Point cur = q.poll();                

                for(int i=0; i<4; i++){
                    int nextR = cur.r + dr[i];
                    int nextC = cur.c + dc[i];

                    if(nextR >= N || nextR <= -1 || nextC >= K || nextC <= -1 || map[nextR][nextC] == 0){
                        continue;
                    }

                    if(dist[nextR][nextC] != 0){
                        continue;
                    }


                    dist[nextR][nextC] = dist[cur.r][cur.c] + 1;
                    q.add(new Point(nextR, nextC));                    
                }

                
            }

            System.out.println(dist[N-1][K-1] - 1);
        
            

        }
    }

    class Point{
        int r,c;
        Point(int r, int c){
            this.r =r;
            this.c = c;
        }
    }

 

 

bfs로 최단거리를 계산하는 예시이다.