99클럽 코테 스터디 23일차 TIL [조합 - 백트래킹]

- 오늘의 학습 키워드 : 조합(백트래킹)

[문제 이름 : 치킨 배달 (백준, G5)]
문제 url : https://www.acmicpc.net/problem/15686

내가 작성한 코드는 아래와 같다.

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

public class Main {
    static int n,m;
    static ArrayList<int[]> house = new ArrayList<>();
    static ArrayList<int[]> chicken = new ArrayList<>();
    static int minDistance = 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());

        for(int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                int num = Integer.parseInt(st.nextToken());
                if(num == 1) house.add(new int[]{i,j});
                else if(num == 2) chicken.add(new int[]{i,j});
            }
        }

        combination(new ArrayList<>(), 0);
        System.out.println(minDistance);
    }

    static void combination(ArrayList<int[]> selected, int start) {
        if(selected.size() == m) {
            // 선택된 치킨집에 대해 최소 거리 계산
            int totalDistance = 0;
            for(int[] h : house) {
                int minDist = Integer.MAX_VALUE;
                for(int[] c : selected) {
                    int dist = Math.abs(h[0] - c[0]) + Math.abs(h[1] - c[1]);
                    minDist = Math.min(minDist, dist);
                }
                totalDistance += minDist;
            }
            minDistance = Math.min(minDistance, totalDistance);
            return ;
        }

        for(int i=start; i<chicken.size(); i++) {
            selected.add(chicken.get(i));
            combination(selected, i+1);
            selected.remove(selected.size()-1);
        }
    }
}

풀이 과정(풀이 시간 : 2시간)

조합인 걸 알았지만, 해당 방법으로 문제를 푸는 게 익숙하지 않아 다른 방법이 있나 찾아보다가,, 포기했다.

조합, 순열 및 백트래킹 문제도 기업 코테에서 자주 나오는 문제니, 꼭 숙달을 해놔야겠다고 생각했다.

 

1. 문제에서 배열 내에 벽 같은 게 존재하지 않으니, 가정집과 치킨집을 house, chicken인 ArrayList로 저장해주었다.

2. 모든 조합을 확인해보면서, 개수가 m개일 때 각자의 가정집에서 치킨집까지와의 최소 거리를 구한 다음, 이를 전체 거리와 다시 최소 거리를 비교해가며 값을 갱신한다.

3. 이렇게 나온 최소 거리가 m개의 치킨집일 때 각 가정집에서 나온 최소 거리이므로, minDistance를 리턴해주면 된다.