백준 15686 치킨 배달 Java

삼성 SW 역량테스트 기출 문제인 치킨 배달 문제이다.

구현하기 쉬운편의 문제이지만 해결하는데 생각보다 오래 걸렸다.

 

문제에서 주어진 치킨집과 집의 거리를 구하는 공식을 사용하지 않고

BFS로 치킨집과 집의 거리를 구하려고 했던 잘못도 있고

 

M개의 치킨집을 살릴 때의 모든 경우를 DFS로 구해내는데

조금 시간이 걸렸다. 왜냐하면 재귀 호출시에 파라미터로 어떤 List나 배열을

넘길 때 List나 배열이 추가되고 초기화 되는 부분이 헷갈린다.

그 부분이 헷갈려서 자꾸 문자열로 처리하려는 습관이 있었는데

이 문제, 야구게임 문제 등 몇 개의 문제를 풀면서 확실히 개념이 잡힌 것 같다.

 

모든 경우를 구할 때 문자열보단 배열을 초기화하는 방식이 훨씬 빠르므로

다른 문제에 적용해보면서 더 연습해봐야겠다.

 

문제를 푸는 방법은 매우 간단하다.

1. M개의 치킨집을 살리는 모든 경우를 구한다.

2. M개의 치킨 조합이 완성되면 각각의 집에서 가장 가까운 치킨집과의 거리를 구한다.

3. 각각의 집별로 구해진 거리를 더하면서 가장 작은 도시의 치킨거리를 구한다.

 

import java.io.*;
import java.util.*;
 
public class Q15686 {
    static int n;
    static int m;
    static List<Integer> chickens = new ArrayList<>();
    static List<Integer> homes = new ArrayList<>();
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for(int i=0; i<n; i++) {
            st = new StringTokenizer(reader.readLine());
            for(int j=0; j<n; j++) {
                int v = Integer.parseInt(st.nextToken());
                if(v == 2) chickens.add((i*n)+j);
                else if(v == 1) homes.add((i*n)+j);
            }
        }
        dfs(new int[m], 0, 0);
        System.out.println(min);
    }
    
    static void dfs(int[] temp, int idx, int cnt) {
        if(cnt==m) {
            int sum = 0;
            for(int i=0; i<homes.size(); i++) {
                sum += calc(temp, homes.get(i));
                if(sum > min) break;
            }
            min = Math.min(sum, min);
            return;
        }
        if(idx >= chickens.size()) return;
        temp[cnt]=chickens.get(idx);
        dfs(temp, idx+1, cnt+1);
        dfs(temp, idx+1, cnt);
    }
    
    static int calc(int[] temp, int idx) {
        int dist = Integer.MAX_VALUE;
        int r1 = idx/n;
        int c1 = idx%n;
        for(int i=0; i<temp.length; i++) {
            int r2 = temp[i]/n;
            int c2 = temp[i]%n;
            dist = Math.min(dist, Math.abs(r1-r2)+Math.abs(c1-c2));
        }
        return dist;
    }
}