탐색 알고리즘 문제 풀어보기 2(백준 13023번 친구 관계 파악하기)(feat. 백트래킹)

지난번에는 DFS와 BFS모두를 이용해서 해결할 수 있는 문제를 풀어보았다. 그러면 오늘의 문제도 과연 그것이 가능할까?

https://www.acmicpc.net/problem/13023

13023번: ABCDE

이 문제는 친구 관계(양방향 간선 그래프)가 주어졌을 때 5명 이상 연속된 친구관계가 존재하느냐를 찾는 문제이다. 처음 문제를 딱 보면 5명이 연속해서 있어야 하니 깊이를 이용해야겠구나 하는 생각이 들었다. 그러면 자연스럽게 DFS가 떠오르게 된다. 이 문제는 DFS탐색을 통해 깊이가 5 이상인지 알아보는 문제이다.

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

public class Main {
    static ArrayList<Integer>[] people;
    static boolean[] visited;
    static boolean ans;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        people = new ArrayList[N];
        for(int i=0;i<N;i++){
            people[i] = new ArrayList<Integer>();
        }
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            people[a].add(b);
            people[b].add(a);
        }
        for(int i=0;i<N;i++){
            visited = new boolean[N];
            search(i,1);
            if(ans){
                bw.write("1");
                bw.flush();
                bw.close();
                System.exit(0);
            }
        }
        bw.write("0");
        bw.flush();
        bw.close();
    }
    static void search(int node, int cnt){
        if(cnt==5){
            ans = true;
            return;
        }
        visited[node] = true;
        for(int i:people[node]){
            if(!visited[i]) search(i, cnt+1);
        }
        visited[node] = false;
    }
}

문제의 핵심 알고리즘 자체는 DFS를 이용하여 어렵지 않게 구현할 수 있었다. 함수의 매개변수로는 현재 번호와 깊이를 주어 깊이가 5가되면 정답 변수를 참으로 바꾸어 1을 출력하도록 하였다. 제일 어려웠던 부분은 맨 마지막 구문인 현재 노드를 방문하지 않도록 바꾸어주는 것이었다. 이것을 백트래킹이라고 하는데 처음에는 이게 왜 필요한지 몰라 문제를 계속 틀렸는데 몇 가지 예시를 직접 해보고 나서야 알 수 있었다. 만약 앞쪽에서 1번을 방문했는데 1번 후로 연결된 친구가 5명이 안돼서 실패하고 3번의 친구 중에 1번이 있어 깊이가 5가 된다고 생각해 보자. 만약 저 구문이 없으면 1번을 탐색하고 실패하였을 때 방문 배열에서 1번이 방문을 완료한 것으로 처리된다. 정작 3번의 친구로 방문할 1번은 탐색 시작도 안 했는데 말이다! 3번을 탐색하면 1번이 이미 방문했다고 체크되어 있어 방문을 안 하고 넘어가고 그러면 알고리즘이 꼬이기 시작한다. 따라서 탐색에 실패했다면 방문을 했더라도 안 했다고 체크해주어야 한다. 이것이 백트래킹 기법이다. 만약 깊이가 5가 된다면 해당 구문은 실행되더라도 답은 이미 정답변수에 저장이 되어 답에 영향을 주지 않는다.

만약 이 문제를 BFS로 풀면 어떨까? 완전히 불가능하지는 않을 것이다. 하지만 한군데라도 깊이 5가 되면 바로 탐색을 멈추고(더 깊이 들어가지 않고) 답을 출력하는 DFS에 비해 BFS는 모든 사람에 대해 깊이 5까지는 전부 연산을 해야 한다. 이 과정에서 서로 친구인 사람들은 따로 처리를 해주어야 하고 알고리즘이 약간 복잡해진다. 만약 순환관계라도 있으면 더욱 복잡해질 것이다. 따라서 이 문제는 DFS로 푸는 것이 더 효과적이라고 볼 수 있다.