[백준 / Java] 15686: 치킨 배달 (백트래킹)

난이도: Gold 5

문제: https://www.acmicpc.net/problem/15686

 

N의 크기는 50으로 작다.

하지만 N의 크기가 작다고 이중 for문을 돌려버리면 시간 초과가 떠버린다.

이중 for문은 시간복잡도가 O(n^2)이니까 50 * 50 = 2500이면 충분하지 않은가? 라고 생각할 수도 있지만 절대 그렇지 않다. 이중 for문을 사용하면 시간 복잡도는 생각보다 어마어마하다.

M의 개수는 최대 13개. 즉, dfs로 13번 파고들면 이중 for문을 13번이나 돌려야 한다.

즉,

 

for (1~50)
     for (1~50)
          for (1~50)
              for (1~50)
                   for (1~50)
                        for (1~50)
                             for (1~50)
                                  for (1~50)
                                      for (1~50)
                                          for (1~50)
                                              for (1~50)
                                                  for (1~50)
                                                      for (1~50)

                                                                     

                                                                          ....

                                                                                       

                                                                                           for (1~50)

                                                                                               for (1~50)

 

이런 상황이 되므로 M이 값이 크다면 절대 1초안에 문제를 해결할 수 없다.

 

그러면 어떻게 하느냐?

어차피 집과 치킨집의 위치는 바뀌지 않고 개수도 고정되어 있다.

하지만 몇 개씩 만들어지는지 숫자로 직접적으로 알려주지는 않는다.

그러므로, 가변적인 ArrayList를 사용해서 집과 치킨집의 리스트를 만들면 된다.

이렇게 하면 for문 1개로도 간편하게 해결할 수 있다.

 

그 이후, 백트래킹 코드만 제대로 작성하면 이 문제를 해결할 수 있다.

여기서 주의할 점은 dfs로 파고들 때 depth 1 증가하면 정하면 안되고, index도 반드시 1 증가해서 매개변수로 넘겨주어야 한다는 것이다.  그렇지 않으면 또 시간 초과가 발생한다..

2중 for문을 1중으로 바꾸었으니 시간 초과가 나면 안되는 것 아닌가? 라고 생각했지만 사실 이것도 1~13까지의 for문을 13번을 돌린다면 13중 for문을 돌려야 한다.

13^13을 계산기에 두드려보니 e라는 영어가 보였다. 숫자가 엄청나게 크다는 뜻이다. 1억보다도 훨씬 크니까 절대 1초 내에 문제를 해결할 수 없다.

그러므로 dfs로 파고들 때 매개변수로 index를 1 증가시킨 값도 같이 전달해야 한다는 것이다.

이전에 탐색한 값들은 어차피 건너뛸 것이기 때문에 index + 1부터 탐색해도 상관이 없다.

쓸데없이 처음부터 계속 탐색하지 않아도 되어서 훨씬 효율적이다.

이러면 시간 초과도 발생하지 않는다.

 

주석에 문제를 해결하는 과정을 한 줄 한 줄 자세하게 써 놓았다.

자, 이제 코드를 보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class P15686_치킨배달 {
    static int N;                        // 2차원 도시 배열의 행, 열 개수
    static int M;                        // 폐업시키지 않을 치킨집의 개수
    static ArrayList<Point> houses;      // 집 좌표 리스트
    static ArrayList<Point> chickens;    // 치킨집 좌표 리스트
    static int[] open;                   // 오픈한 치킨집 인덱스 배열
    static boolean[] selected;           // 치킨집의 오픈 여부 배열
    static int minCityChickenLength;     // 도시의 치킨 거리의 최솟값    
    
    static class Point {
        int x, y;
        
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());    
        M = Integer.parseInt(st.nextToken());    
        houses = new ArrayList<>();
        chickens = new ArrayList<>();
        open = new int[M];
        minCityChickenLength = Integer.MAX_VALUE;
        
        // 2차원 도시 배열 초기화
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                int spot = Integer.parseInt(st.nextToken());
                if (spot == 1) {
                    houses.add(new Point(i, j));    // 집 좌표 리스트에 값 삽입
                } else if (spot == 2) {
                    chickens.add(new Point(i, j));    // 치킨집 좌표 리스트에 값 삽입
                }
            }
        }
        
        // 치킨집 오픈 여부 배열의 사이즈를 치킨집의 개수만큼 정해주고 초기화
        selected = new boolean[chickens.size()];    
        
        // M개의 치킨집을 선택한 경우의 수를 모두 탐색해야하므로 백트래킹 수행
        dfs(0, 0);
        
        System.out.println(minCityChickenLength);    // 도시의 치킨 거리의 최솟값 출력
    }
    
    public static void dfs(int depth, int index) {
        // M개의 치킨집을 모두 선택했으면 
        // M개의 치킨집을 선택한 도시의 치킨 거리 계산 후 함수 종료
        if (depth == M) {
            int cityChickenLength = 0;    // M개의 치킨집을 선택한 도시의 치킨 거리
            
            for (Point house : houses) {    // 집들 모두 탐색
                // 해당 집과 치킨집들 사이의 거리중 가장 작은 값
                int chickenLength = Integer.MAX_VALUE;
                
                for (int i = 0; i < M; i++) {    // 오픈한 치킨집 모두 탐색
                    // open[i]: i번째로 오픈한 치킨집의 인덱스
                    // chicken: open[i]번째 치킨집
                    Point chicken = chickens.get(open[i]);
                    // 해당 집과 해당 치킨집 사이의 거리
                    int length = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);
                    // 해당 집과 치킨집들 사이의 거리 최솟값 갱신
                    chickenLength = Math.min(chickenLength, length);
                }
                
                // 해당 집의 최소 치킨 거리를 찾았으면 도시의 치킨 거리에 더하기
                cityChickenLength += chickenLength;
            }
            
            // 도시의 치킨 거리의 최솟값 갱신
            minCityChickenLength = Math.min(minCityChickenLength, cityChickenLength);
            return;        // 함수 종료 후 다른 치킨집 오픈하러 가기
        }
        
        // 백트래킹
        // 0 ~ chicken.size() - 1번째 치킨집 모두 탐색
        // 오픈된 치킨집은 총 M개이므로, depth번째 치킨집도 M번 들어가야 함(인덱스는 M - 1까지)
        for (int i = index; i < chickens.size(); i++) {            
            if (!selected[i]) {            // i번째 치킨집이 폐업 상태라면
                selected[i] = true;        // i번째 치킨집 오픈시키기
                open[depth] = i;        // depth번째 오픈된 치킨집 = i번째 치킨집
                // depth + 1번째 치킨집 오픈하러 가기
                // 앞에는 이미 탐색했으므로 i + 1번째부터 탐색해야 시간 복잡도가 줄어듦
                dfs(depth + 1, i + 1);    
                selected[i] = false;    // i번째 치킨집 폐업시키기
            }
        }
    }
}