2 - 3. DFS 예제 (1260번: DFS와 BFS), DFS 응용

백준 1260번(DFS와 BFS)

후.. 몇일 전에 작계 훈련 갔다오고, 또 지원서 쓰느라 이제야 포스팅 합니다. ㅠㅠ

이 문제는 한창 DFS를 잘 모르고 문제를 막 풀어댈 때 겁나 털린 문제입니다.

정말 기본기만 할 줄 안다면, 바로 풀 수 있는 문제이고, DFS 연습 및 구조 파악하기 좋습니다.

이 문제 말고도 N과 M이라는 문제 시리즈가 있는데, 저는 그 문제를 통해서 DFS 및 Back Tracking에 대해 제대로 알게 되었어요.

어쨌든 각설하고 문제부터 읽어 봅시다.

문제

---

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

---

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

---

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

기본 문제 답게 문제 조건도 매우 단조롭습니다.

지난번 BFS, DFS 설명때 제가 써둔 BFS, DFS 코드를 제대로 알고 계신다면 굳이 풀이를 안보셔도 상관없습니다.

그 정도로 기본적인 문제입니다. (정답률은 왜 그런지 잘 모르겠지만요...)

시작 정점이 주어졌으니, 여러번 돌릴 필요 없이 V라는 정점에서 1회 탐색으로 끝내면 되겠네요.

그리고 양방향 그래프라는 것과 길이 여러개일 경우 번호가 작은 노드 부터 탐색한다. 라는 것만 주의하면 되겠습니다.

그리고, BFS에 대한건 이미 앞의 포스팅에서 많이 했기 때문에 DFS에 대한 설명만 하고 바로 코드로 넘어갈게요.

문제의 입력 조건에 맞춰서 함수가 실행되고 반환되는 움직임을 설명해 보겠습니다.

입력에 맞춰 인접리스트를 그리고 V가 1이니까 1부터 탐색하는 것으로 보여드릴게요.

함수는 스택과 같이 동작하기 때문에 스택을 이용해서 설명 드리겠습니다.

우선 1번 탐색 실시합니다.

1번이 방문된 것으로 설정되고, 출력 값에 [1] 이렇게 저장됩니다.

2번도 1번과 같이 처리해주고, 출력 값에 [1 2]라고 저장이 됩니다.

2에서는 갈 수 있는 노드가 4번 뿐이니 4번부터 탐색합니다.

그리고 4번도 똑같이 처리하고 [1 2 4]라고 저장이 됩니다.

마지막으로 3번 탐색 후 이런식으로 함수들이 대기하게 됩니다.

출력 값은 [1 2 4 3] 입니다.

결과 코드

package depth_first_search;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
/**
 * 
 *     @author minchoba
 *    백준 1260번 : BFS 와 DFS
 *
 *    @see https://www.acmicpc.net/problem/1260
 *
 */
 
public class Boj1260 {
    private static final String SPACE = " ";
    private static final String NEW_LINE = "\n";
    
    private static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), SPACE);
 
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());
        
        ArrayList<Integer>[] graph = new ArrayList[N + 1];
        
        boolean[] isVisited = new boolean[N + 1];
        
        for(int i = 0; i < N + 1; i++){                                            // 인접 리스트 내부 초기화 
            graph[i] = new ArrayList<>();
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), SPACE);
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            
            graph[from].add(to);
            graph[to].add(from);
        }
        br.close();
        
        for(int i = 1; i < N; i++){                                                // 인접 리스트 입력 값 정렬
            Collections.sort(graph[i]);
        }
        
        dfs(V, graph, isVisited);                                                // dfs 실행 메소드
        
        isVisited = new boolean[N + 1];
        sb.append(NEW_LINE);
        
        bfs(V, graph, isVisited);                                                // bfs 실행 메소드
        
        System.out.println(sb.toString());                                // 버퍼에 담긴 노드 방문 순서를 한번에 출력
    }
    
    private static void dfs(int current, ArrayList<Integer>[] graph, boolean[] isVisited){
        if(isVisited[current]) return;
        isVisited[current] = true;    
                
        sb.append(current).append(SPACE);            // 현재 방문한 노드값을 버퍼에 담아둠
        
        for(int next : graph[current]){                // next 변수에 현재 방문한 노드에 해당하는 리스트에 담겨있는 값들을 하나씩 할당
            if(!isVisited[next]){                    
                dfs(next, graph, isVisited);        // 다음 방문할 노드 값으로 바꾸어 재귀 함수 실행
            }
        }
    }
    
    private static void bfs(int current, ArrayList<Integer>[] graph, boolean[] isVisited){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(current);
        isVisited[current] = true;
        
        while(!queue.isEmpty()){
            current = queue.poll();
            sb.append(current).append(SPACE);
            
            for(int next : graph[current]){
                if(!isVisited[next]){
                    isVisited[next] = true;
                    queue.add(next);
                }
            }
        }
    }
}
 

채점 결과

BackTracking...?

상당히 쉽죠. 근데 이렇게 자세하게 그림까지 그려가며 한 이유가 있습니다.

조금 다른 코드로 설명을 드릴게요.

시리즈가 있는 'N과 M'이라는 문제에 대한 코드와 유사한데요.

함수가 호출되고 반환되는데에 따라 파라미터 값들이 어떻게 변하는지 간략하게 보여드리도록 하겠습니다.

1 2 3 4 라는 숫자로 순열의 개수를 뽑는다고 가정해 보겠습니다.

1 2 3 4, 1 2 4 3, 1 3 2 4 ....... 4 3 2 1

이렇게 모두 출력해야한다면, 일반적인 깊이 우선 탐색으론 안되겠다는 것을 아실겁니다.

사실 뭐 특정 알고리즘이다 라고 보긴 어렵고 제가 느끼기엔 깊이 우선 탐색을 응용한 정도?라고 생각합니다.

이러한 문제에 대한 코드는 아래와 같습니다.

BackTracking.java

public class Main {
    private static boolean[] isVisited;
    private static StringBuilder sb = new StringBuilder();
    
    private static final String NEW_LINE = "\n";
    private static final String SPACE = " ";
    
    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 3, 4};
        
        for(int i = 1; i < nums.length; i++) {
            isVisited = new boolean[nums.length];
            backTracking(nums, i, 0, nums[i] + "");
        }
        
        System.out.println(sb);
    }
    
    private static void backTracking(int[] arr, int current, int count, String seq) {
        if(count == arr.length - 2) {
            sb.append(seq).append(NEW_LINE);
            return;
        }
        
        if(isVisited[current]) return;
        isVisited[current] = true;
        
        for(int next = 1; next < arr.length; next++) {
            if(isVisited[next]) continue;
            
            backTracking(arr, next, count + 1, seq + SPACE + arr[next]);
            isVisited[next] = false;
        }
    }
}

일반 DFS랑 조금 다른점이 보이시나요?

1 ~ 4번 인덱스까지 완전 탐색을 하는데, 

메소드 내부에 반복문이 들어가고 함수 호출 밑 부분에 방문 배열을 방문하지 않음으로 초기화 합니다.

이 부분이 백트래킹을 위한 파트입니다.

그리고 String seq는 순열을 만들기 위해 지정한 문자열 변수입니다.

방문 배열과 함수의 호출 및 반환 그리고 그에 따른 seq가 변경되는 작동을 자세히 보여드릴게요.

우선 기본적으로 인덱스 1 ~ 4 까진 쭉 들어갈테니 그 상황에서 시작하겠습니다.

이제 여기서 다음 순열을 찾아야하죠. 다음 순열은 [1 2 4 3] 입니다.

따라서 이 순열을 만들기 위해선 아래의 순서로 돌려야합니다.

1. 4번을 가진 함수를 반환한다.

2. 3번을 가진 함수를 반환한다.

3. 4번을 가진 함수를 호출한다.

4. 3번을 가진 함수를 호출한다.

1.에서 4번 함수 호출은 조건문 'if(count == arr.length - 2)'에 걸리면서 반환이 됩니다.

즉 순열 크기만큼 돌고 범위를 벗어나기전에 반환된 것 입니다.

그리고 2.에서 3번 함수 호출은 4번이 반환되면서 32번째 줄로 가게되는데, 이때 남은 반복문이 돌게되는 것이죠.

반복문의 상태 next에는 4의 값이 들어있고, 따라서 isVisited[4]이 false 값으로 변경됩니다.

그리고 'next = 4'인 반복문이 끝나고 반복문을 탈출하면, 다음 스택에 들어있는 함수를 반환하게 되겠죠?

그래서 다음으로 3번 함수가 반환되고 isVisited[3] 값도 false가 됩니다.

그리고 어떻게 될까요? 3번을 아직 방문 안함으로 바꿨고, 그 다음 next = 4 이렇게 됩니다.

따라서 4번을 가진 함수를 다시 호출하고, 그 다음엔 호출한 4번 함수에서 count가 아직 부족하니까 반복문을 돌겠죠.

반복문을 돌리면 그땐 3번 말고 호출 할 수 있는 함수가 없으니, 3번 호출 후 다음 순열을 만들어 내게 됩니다.

이를 그림을 통해 설명드려 보겠습니다.

초기 상태

4번 함수 반환 상태

3번 함수 반환 상태

4번 함수 재호출 상태

3번 함수 재호출 상태

결과

이 짧은 구간 동안의 동작을 이해하시면, 전체적으로 어떻게 작동하는지 이해하실 수 있습니다.

암산으로 하기보단 직접 그려보시면서 전체적인 흐름을 파악하시길 바랍니다.

저는 사실 백트래킹이 어렵게 느껴졌던건 정확한 정의가 없다는 느낌(?) 때문이었습니다.

백트래킹은 그냥 역 추적에 가지치기를 한다. 정도로만 저는 이해했습니다.

특히 가지치기 같은 부분은 코드를 짜다보면 문제에따라 하긴하는데, 무조건 적으론하진 않아서..ㅠ

요점은 그냥 본인의 스타일에 맞게 계속 짜보고 여러 글들을 찾아 읽어 보시라고 말씀드리고 싶습니다.

백트래킹의 시간복잡도는 일반적으로 지수함수입니다. O(n^k) 꼴

(물론, 위의 경우엔 O(4!) 입니다.)

factorial, 지수 모두 수가 조금만 커져도 일반적인 시간 제한으로는 커버가 안됩니다.

또한, 경우에 따라 다르므로 반드시 계산 해보시고 접근하세요!!

연습이 충분히 되셨다면, N과 M 시리즈는 모두 풀어보시는 것을 추천 드립니다.

그리고 백트래킹의 대표적인 문제 NQueen도 풀어보시길 바랍니다.

기회가 된다면 해당 문제에 대한 풀이도 올리도록 할게요.

이해안가는 것이나, 질문 또는 잘못된 부분은 댓글로 지적 부탁드려요. 감사합니다.

문제의 저작권은 백준 온라인 저지에 있습니다.