15686번 문제

문제

풀이

처음엔 풀이방법을 다음과 같이 짰다.

1. 각 집에 대해 가장 가까운 치킨 집에 치킨 거리를 저장한다.
2. 이후, 치킨 집에 저장된 치킨 거리의 합이 최소가 되도록 M개의 치킨 집을 고른다.

하지만 위의 방법대로 풀이하면 답이 나오지 않는다.
M개의 치킨 집을 선택하고 나면, 선택되지 않아 사라지는 치킨 집에 저장되었던 치킨 거리는 고려되지 않기 때문이다.

따라서 결국 M개의 치킨 집을 선택하는 모든 경우의 수를 전부 따져보아야 하는 문제였다.

따라서 백트래킹을 통해 문제를 풀었다.

첫 번째 풀이

제출 코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static int min = Integer.MAX_VALUE;
    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());
        map = new int[N+1][N+1];

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

        chooseChickenPlace(0);
        System.out.println(min);
    }

    public static void chooseChickenPlace(int depth) {
        if(depth == M) {
            int sum = getSumOfChickenDistance();
            if(sum < min) {
                min = sum;
            }
            return;
        }

        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(map[i][j]>1) {
                    map[i][j] = -1; // 현재 선택한 치킨 집은 -1로 마킹
                    chooseChickenPlace(depth+1);
                    map[i][j] = 2;
                }
            }
        }
    }

    // 도시의 치킨 거리 값을 반환
    public static int getSumOfChickenDistance() {
        int sum = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(map[i][j] == 1) {
                    sum += getChickenDistance(i, j);
                }
            }
        }
        return sum;
    }

    // 해당 좌표의 집에서 가장 가까운 치킨집을 찾아 치킨 거리를 반환
    public static int getChickenDistance(int row, int col) {
        int chickenDistance = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if((map[i][j] == -1) && (Math.abs(row-i)+Math.abs(col-j) < chickenDistance)) {
                    chickenDistance = Math.abs(row-i)+Math.abs(col-j);
                }
            }
        }
        return chickenDistance;
    }
}

코드로 구현하는 것은 심플했다.
한 가지 고려해야할 점은 도시의 칸이 0이 아닌 1로 시작한다는 점이다.

위 코드로 모든 테스트케이스를 통과하여, 그대로 제출해보았지만 결과적으로 시간초과였다.

두 번째 풀이

사실 어느정도 예상한 결과였다. 왜냐면 풀이에 사용되는 모든 메서드마다 O(N^2)의 시간복잡도를 가지고 있었기 때문 ...
따라서 아래의 변경사항을 적용하였다.

1. 치킨집과 집의 좌표를 따로 저장하는 자료구조를 사용한다.
   → getSumOfChickenDistance()와 getChickenDistance()의 시간복잡도를 줄임
2. chooseChicken()에 idx를 두어 오름차순으로만 순회한다.

제출 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static int N, M;
    static int[][] map;
    static List<int[]> chickenPlaces = new ArrayList<>();
    static List<int[]> houses = new ArrayList<>();  
    static int min = Integer.MAX_VALUE;
    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());
        map = new int[N+1][N+1];

        for(int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==1) {
                    houses.add(new int[] {i,j});
                } else if(map[i][j]==2) {
                    chickenPlaces.add(new int[] {i,j});
                }
            }
        }

        chooseChickenPlace(0,0);
        System.out.println(min);
    }

    public static void chooseChickenPlace(int idx, int depth) {
        if(depth == M) {
            int sum = getSumOfChickenDistance();
            if(sum < min) {
                min = sum;
            }
            return;
        }

        for(int i=idx; i<chickenPlaces.size(); i++) {
            int[] cur = chickenPlaces.get(i);
            if(map[cur[0]][cur[1]]>1) {
                map[cur[0]][cur[1]] = -1; // 현재 선택한 치킨 집은 -1로 마킹
                chooseChickenPlace(i+1, depth+1);
                map[cur[0]][cur[1]] = 2;
            }
        }
    }

    // 도시의 치킨 거리 값을 반환
    public static int getSumOfChickenDistance() {
        int sum = 0;
        for(int i=0; i<houses.size(); i++) {
            int[] cur = houses.get(i);
            sum += getChickenDistance(cur);
        }
        return sum;
    }

    // 해당 좌표의 집에서 가장 가까운 치킨집을 찾아 치킨 거리를 반환
    public static int getChickenDistance(int[] hPos) {
        int chickenDistance = Integer.MAX_VALUE;
        for(int i=0; i<chickenPlaces.size(); i++) {
            int[] cPlace = chickenPlaces.get(i);
            if(map[cPlace[0]][cPlace[1]]<0) {
                if(Math.abs(hPos[0]-cPlace[0])+Math.abs(hPos[1]-cPlace[1]) < chickenDistance) {
                    chickenDistance = Math.abs(hPos[0]-cPlace[0])+Math.abs(hPos[1]-cPlace[1]);
                }
            }       
        }
        return chickenDistance;
    }
}

결과는 성공 !

---

백트래킹을 사용하는 메서드에서는 idx를 통해 for문의 반복을 줄여주는게 매우 중요하다는 것을 다시금 깨닫게 된 문제였다.