백준(BOJ)-1260 DFS와 BFS (DFS,BFS 알고리즘)

문제

문제 이해 및 코드

DFS와 BFS 개념은 이해하고 풀어야 하는 문제이다. 처음에 4 5 1 을 입력하면 N=4, M=5, start =1 이지만, 편하게 이해하기위해서 N=N+1을 해준다. 보통 DFS와 BFS 문제는 map을 먼저 그려놓고 , 내가 탐색해야하는 부분에 미리 1을 저장시켜놓고 1인 부분을 찾아가는 식으로 이해하면 조금이나마 이해하기가 쉽다. 첫번째 예제의 조건을 보면, 간선을 연결하는 두 정점의 번호가 (1 2) (1 3) (1 4) (2 4) (3 4)라고 되어있으며 양방향이라고 했기때문에 우선 그림을 그려서 map 이차원 배열에다가 탐색해야하는 부분에 1을 넣어주었다.

 

현재 N=4, M=5, start = 1일 경우 map[N+1][N+1]을 만들어서 앞에는 From 뒤에는 To 인 순서쌍으로 되어 있을 경우 (1 2) (1 3) (1 4) (2 4) (3 4) 와 양방향까지 생각해줄 경우 다시 (2 1) (3 1) (4 1) (4 2) (4 3)에다가 1이라는 값을 넣어준다. 우선 여기까지 코드로 짜보면

 

public class BOJ_1260_DFS_BFS {
    static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken())+1;
        int M = Integer.parseInt(st.nextToken());
        int start = Integer.parseInt(st.nextToken());

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

가 된다.

 

DFS

이해를 위한 그림

이제 문제의 조건에맞추어서 dfs 탐색을 해야하는데, visited는 방문확인 여부를 위해 만든 배열이며 이것도 고려 해야 한다. 처음에 start 가 1이기 때문에 visited[1]은 1로 초기화 시켜준다. 현재 상태는 Visited[0,1,0,0,0] 이다. 다음으로 1부터 탐색(from 1)을 하는데 다시 위의 그림을 보면, map 배열에서 from(1)이 즉, start =1 이 들어온경우에 to(1)는 map의 값(map(1 1))이 0이기 때문에 고려하지 않아도 되고, map(1 2) 를 우선 탐색하게 된다. 그경우에 현재 map[1][2]도 1이고, visited[2]도 0이기 때문에 즉, 내가 원하는 탐색정점과 방문하지 않았다는 조건을 모두 만족하기 때문에 from(1)에서 to(2)로 들어가게 된다 (현재 Visited[0,1,1,0,0]) . 이제 from이 2로 가게 되고, map을 보면 from이 2일경우 to는 1과 4가 있지만, 1은 visited[1]이 이미 1이 되어버렸기 때문에, 4인 경우로 탐색하게 된다. 

현재까지 정리해보면
1 -> 2 -> 4이며,
visited = [0,1,1,0,1]

마지막으로 4일때, map의 to를 보면, 1,2,3으로 갈수 있지만, Visited가 0 (즉 아직 방문하지 않은 곳)은 3밖에 없기 때문에 3을 탐색하게 된다. 이제 이런 이론을 가지고 코드를 짜보면,

public static void dfs(int idx, int visited[], int map[][]){
        int fr = idx;
        visited[fr] = 1;
        System.out.print(fr+" ");
        for(int i=1;i<N;i++)
        {
            if(map[fr][i]==1 && visited[i]==0)
            {
                dfs(i, visited, map);
            }
        }
    }

위에서 이론적으로 설명했듯이, 우선 방문할때마다 visited배열에다가 현재 숫자를 넣어주며, 바로 출력해준다. For문은 처음에 idx가 당연히 start = 1이기때문에 map[1][i]부터 시작해서 위의 그림의 Map배열을 확인하는 반복문이다. 그때 map에 1이 있고 visited가 0이면(원하는 목적지와 방문하지 않았을경우) 재귀 함수를 이용하면 위의 순서처럼 dfs(1)->dfs(2)->dfs(4)->dfs(3)이 돌게되며 출력값은 1 2 4 3이 나오게 된다.

 

 

BFS

보통 dfs는 스택이나 재귀함수를 이용하는 반면에, bfs는 큐를 이용한다. 위의 dfs랑 비슷하지만, 이번에도 아까 그린 그림을 참고하면, map의 from 이 1일경우 dfs는 1->2로 가서 다시 2->4 , 4->3순서대로 탐색을 했지만, 넓이 우선탐색인 bfs는 from이 1일 경우 to인 2,3,4를 다 탐색하게 된다. 즉 from이 1로 시작할경우, visited도 다 [0,1,1,1,1]가 되고, 그때마다 큐에다가 집어넣어주면 된다. 이건 코드를 먼저 보면

public static void bfs(int idx,int visited[],int map[][])
    {
        Queue<Integer> q =  new LinkedList<>();
        q.add(idx);
        visited[idx] = 1;

        while(!q.isEmpty())
        {
            int cur = q.remove();
            System.out.print(cur+" ");
            for(int i=1;i<N;i++)
            {
                if(map[cur][i]==1&&visited[i]==0)
                {
                    q.add(i);
                    visited[i]=1;
                }
            }
        }
    }

 

처음에 Queue를 생성하고, start인 1을 큐에다가 넣어준다. 

현재 큐 : 1

그러면서 dfs에서는 재귀 함수를 통해 반복해주었다면, bfs에서는 큐에있는 값의 존재 유무에 따라 반복을 돌리면 된다.

큐에 있는 1이 remove를 통해 제거됨과 동시에 cur에다가 집어넣어주며, 그때 반복문 을 보면 현재 큐에있는 1이 cur로 옮겨가면서 시작한다. 그때 조건(내가 탐색해야하는 map에서 1이라고 그린 부분들)과 visited에 만족될때마다 큐에 집어넣어주면 된다. 그러면 처음 큐에 1이 들어갔던값이 출력 되면서 1, 그리고 2,3,4 순서대로 출력된다. 

 

후기

처음에 bfs와 dfs 개념자체는 이해하고 있었지만, 코드로 작성하려니깐 정말 어려웠다. dfs와 bfs는 코딩테스트 문제에서 자주 나오는 문제라는데 기본문제라서 실버2단계밖에 되지않지만, 처음하는 사람 입장으로써는 꽤나 어렵다. 그래도 확실히 한번 구현해보니깐 조금더 어려운 문제도 도전 해볼 수 있을 것 같다.