문제 탐색하기

입력 자료 정리

1. N은 배열의 행열 크기이며, M은 뽑을 치킨집 개수이다
2. 이후 들어오는 값은 각 배열 인덱스의 원소값이며,
   0은 빈칸, 1은 도시, 2는 치킨집이다.

해결방법 추론

1. N과 M이 각각 50과 13이다.
   치킨집을 중복없이 뽑는다고 했을 때, 백트래킹으로 시간초과없이 충분히 가능한 문제다
2. 따라서 백트래킹으로 해당 문제를 해결하면 된다.
3. 좌표로 되어 있어서 조금 편하게 하려면 리스트로 치킨집과 도시의 좌표를 관리하면 된다
4. 선택할 치킨집을 M개 뽑은 다음 각 도시에서 뽑은 치킨집과의 거리를 비교하여
   치킨 거리를 구한다음 최솟값을 갱신해서 합산해주면 전체 합산 치킨거리가 나올 것이다
5. 이때 최솟값이 되도록 백트래킹을 통해 모든 경우를 비교해서 최솟값으로 갱신한다면
   정답을 쉽게 구할 수 있다.
6. 뽑은 치킨집에 대해서는 방문 배열을 통해서 확인해주면 될 것이다.

시간복잡도 계산

1. 치킨집을 뽑는 과정에서 치킨집개수Cm의 조합이 발생할 것이고,
   추가로 base condition에서 도시와 치킨집을 비교하는 과정에서 추가로 연산이 발생한다
2. 이때 base condition에서는 2N x 13이라는 최댓값을 가질 수 있으며,
   시간복잡도로 정리하면 O(치킨집개수Cm x 2N x 13)이라는 결과가 나온다
3. 따라서 시간제한안에 문제를 해결할 수 있다

코드 설계하기

입력값 상태 관리

1. 각 크기를 나타내는 입력값은 n과 m이라는 변수로 관리하며,
   각 인덱스의 값은 a라는 변수에 답고 이어서 분류를 진행한다.
2. 치킨집과 도시의 좌표를 관리할 리스트를 만든 다음 a가 1인경우 도시에 넣고
   2인 경우 치킨집에 넣어주자
3. 방문배열은 치킨집을 뽑는대 사용할 것이므로 치킨집 리스트의 크기로 초기화한다
4. 정답의 초기값은 최솟값을 찾기 위해 Integer.MAX_VALUE로 초기화한다

구현 코드 설계

1. 백트래킹 방문배열 전략을 사용하여 탐색을 진행한다
2. depth가 m이 되면 base condition을 실행하며,
   각 도시를 하나씩 선택해서 선택된 모든 치킨도시와 비교하며 최소가 되는 치킨 거리를 찾는다
3. 그 치킨거리를 합산한 뒤, ans와 비교해서 최솟값으로 갱신한다

출력값 설계

1. 완성한 ans를 출력하면 정답이 될텐데..

시도회차 수정

1회차 시도 실패

1. 1%에서 시간초과가 발생했다. 시간초과가 발생할만한 지점이 없다고 생각했는데
   대체 어디서 발생한 것일까?
2. 다시 코드를 살펴보니 내가 조합 코드를 잘못 작성해놨었다.
   결국 치킨의 크기만큼 모두 순회하므로 최악의 경우 m과 치킨집 최댓값인 13x13이 될 것이고
   이러면 무조건 시간초과가 발생한다
3. 따라서 중복된 치킨집을 선택하지 않도록 start 파라미터를 하나 설정하여
   i+1을 인수로 넘겨주고 탐색할 때 start부터 탐색하도록 한다면
   시간초과없이 문제를 해결할 수 있을 것이다

2회차 시도 성공

1. 해당 방식으로 재풀이 했을 때, 시간초과없이 문제를 해결할 수 있었다

정답 코드

(1회차 실패 코드)

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


public class Main {

    static int[][] arr;
    static ArrayList<int[]> chick;
    static ArrayList<int[]> city;
    static int ans = Integer.MAX_VALUE;
    static boolean[] visited;
    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 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        arr = new int[n][n];
        chick = new ArrayList<>();
        city = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if(arr[i][j] == 1){
                    city.add(new int[]{i,j});
                }else if(arr[i][j] == 2){
                    chick.add(new int[]{i,j});
                }
            }
        }
        visited = new boolean[chick.size()];
        backtracking(n,m,0);

        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static void backtracking(int n, int m, int depth) {
        if(depth == m){
            int sum = 0;
            for (int i = 0; i < city.size(); i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < chick.size(); j++) {
                    if(visited[j]){
                        min = Math.min(min, Math.abs(chick.get(j)[0] - city.get(i)[0]) + Math.abs(chick.get(j)[1] - city.get(i)[1]));
                    }
                }
                sum += min;
            }

            ans = Math.min(ans, sum);
            return;
        }

        for (int i = 0; i < chick.size(); i++) {
            if(!visited[i]){
                visited[i] = true;
                backtracking(n,m,depth+1);
                visited[i] = false;
            }
        }

    }

}

(2회차 정답 코드)

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


public class Main {

    static ArrayList<int[]> chick;
    static ArrayList<int[]> city;
    static int ans = Integer.MAX_VALUE;
    static boolean[] visited;
    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 = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        chick = new ArrayList<>();
        city = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int a =Integer.parseInt(st.nextToken());
                if(a == 1){
                    city.add(new int[]{i,j});
                }else if(a == 2){
                    chick.add(new int[]{i,j});
                }
            }
        }
        visited = new boolean[chick.size()];
        backtracking(n,m,0, 0);

        bw.write(ans+"");

        br.close();
        bw.close();
    }

    private static void backtracking(int n, int m, int depth, int start) {
        if(depth == m){
            int sum = 0;
            for (int i = 0; i < city.size(); i++) {
                int min = Integer.MAX_VALUE;
                for (int j = 0; j < chick.size(); j++) {
                    if(visited[j]){
                        min = Math.min(min, Math.abs(chick.get(j)[0] - city.get(i)[0]) + Math.abs(chick.get(j)[1] - city.get(i)[1]));
                    }
                }
                sum += min;
            }

            ans = Math.min(ans, sum);
            return;
        }

        for (int i = start; i < chick.size(); i++) {
            if(!visited[i]){
                visited[i] = true;
                backtracking(n,m,depth+1, i+1);
                visited[i] = false;
            }
        }

    }

}

문제 링크

15686번 - 치킨 배달