[백준 15686번 / Java] BOJ 15686 : 치킨 배달(DFS)

 

15686번: 치킨 배달

 

 

👇 내가 작성한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N, M;
    static int min = Integer.MAX_VALUE;
    static int[] selected;
    static List<int[]> house = new ArrayList<>();
    static List<int[]> chicken = new ArrayList<>();
    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());
        selected = new int[M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int value = Integer.parseInt(st.nextToken());
                if(value == 1) house.add(new int[] {i, j}); // 집 좌표 저장
                else if(value == 2) chicken.add(new int[] {i, j}); // 치킨가게 좌표 저장
            }
        }
        dfs(0, 0);
        System.out.println(min);
    }

    public static void dfs(int L, int start) {
        if(L == M) { // 유지하는 치킨집 M개 선택 완료되면 dist 메소드 실행
            dist();
            return;
        }

        // 유지할 치킨집 M개 조합하여 selected배열에 인덱스 저장
        for(int i = start; i < chicken.size(); i++) {
            selected[L] = i;
            dfs(L + 1, i + 1);
        }
    }

    public static void dist() {
        int sum = 0;
        for(int[] h : house) {
            int tempMin = Integer.MAX_VALUE;
            for(int idx : selected) { // 유지할 치킨집 M개의 인덱스가 담겨져있는 배열
                int[] hCur = chicken.get(idx);
                int distance = Math.abs(h[0] - hCur[0]) + Math.abs(h[1] - hCur[1]); // 거리 차이 구하기
                tempMin = Math.min(tempMin, distance); // 집에서 가장 가까운 치킨집 선택
            }
            sum += tempMin; // 선택한 치킨거리 누적합
        }
        min = Math.min(sum, min); // 치킨거리 최솟값 구하기
    }
}

 

 

느낀 점 및 정리 ✍️

1. dfs에서 조합 for문 돌릴 때 원하는 방식의 조합 조건이 바로바로 떠오르질 않는다 ㅠㅜ 문제 많이 풀면서 익혀야겠다

2. 거리를 구하는 문제라 어차피 좌표만 알면 돼서 2차원 배열에 별도로 저장하지 않았다