15686번: 치킨 배달

문제

크기가 N×N인 도시가 있습니다. 도시는 1×1크기의 칸으로 나누어져 있습니다. 도시의 각 칸은 빈 칸(0), 집(1), 치킨집(2) 중 하나입니다. '치킨 거리'는 집과 가장 가까운 치킨집 사이의 거리입니다. '도시의 치킨 거리'는 모든 집의 '치킨 거리'의 합입니다. 이 도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 합니다. 어떻게 고르면 도시의 치킨 거리가 가장 작게 될지 구하는 문제입니다.

• 거리 계산 공식: (r1, c1)과 (r2, c2) 사이의 거리는 |r1 - r2| + |c1 - c2| 로 구합니다. (맨해튼 거리)
• 입력: 첫째 줄에 N과 M이 주어지고, 둘째 줄부터 N개의 줄에 도시의 정보가 주어집니다.
• 출력: 폐업시키지 않을 치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최솟값을 출력합니다.

링크: https://www.acmicpc.net/problem/15686

풀이: 백트래킹을 이용한 조합(Combination) 탐색

치킨집의 최대 개수는 13개이므로, 13개 중 M개를 고르는 모든 경우의 수(조합)를 구한 뒤 각각의 치킨 거리를 시뮬레이션하여 최솟값을 찾는 완전탐색 방식으로 해결할 수 있습니다.

1. 좌표 정보 저장: 입력을 받을 때 집(1)과 치킨집(2)의 좌표를 2차원 배열에 기록하지 않고, 바로 Node 객체로 만들어 각각 home 리스트와 chicken 리스트에 담아둡니다. 이렇게 하면 맵 전체를 순회할 필요 없이 필요한 좌표들만 꺼내어 계산할 수 있어 매우 효율적입니다.
2. M개의 치킨집 고르기 (백트래킹): 재귀 함수 go를 사용하여 전체 치킨집 중 M개를 고르는 조합을 생성합니다.
   • idx: 탐색을 시작할 치킨집의 인덱스로, 중복 선택을 방지하기 위해 다음 재귀 호출 시 i + 1을 넘겨줍니다.
   • 현재 선택한 치킨집 인덱스 i를 리스트에 담고(list.add(i)), 탐색을 마친 뒤에는 다른 경우의 수를 찾기 위해 다시 빼줍니다(list.remove(...)).
3. 도시의 치킨 거리 계산 (getChickenDist): M개의 치킨집이 모두 골라졌을 때(list.size() == m), 도시의 치킨 거리를 계산합니다.
   • 각 집(h)마다 선택된 M개의 치킨집(c)들과의 거리를 모두 구하여 가장 짧은 거리를 찾습니다. (chickenDist = Math.min(...))
   • 모든 집의 가장 짧은 거리를 합산(ret += chickenDist)하여 반환합니다.
4. 최솟값 갱신: 반환된 도시의 치킨 거리를 기존의 최솟값(ans)과 비교하여 갱신합니다.

코드

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

public class Main {
    static int n, m;
    // 최솟값을 구해야 하므로 매우 큰 값으로 초기화
    static int ans = Integer.MAX_VALUE; 
    
    // 집과 치킨집의 좌표를 모아둘 리스트
    static List<Node> home = new ArrayList<>();
    static List<Node> chicken = new ArrayList<>();

    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());
       n = Integer.parseInt(st.nextToken());
       m = Integer.parseInt(st.nextToken());

       // 입력 처리: 1은 집, 2는 치킨집 리스트에 바로 추가
       for (int i = 0; i < n; i++) {
          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
             int x = Integer.parseInt(st.nextToken());
             if (x == 1)
                home.add(new Node(i, j));
             else if (x == 2)
                chicken.add(new Node(i, j));
          }
       }

       // 치킨집 M개를 고르는 백트래킹(조합) 시작
       go(0, new ArrayList<>());

       bw.write(ans + "");

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

    // 치킨집 중 M개를 고르는 조합 생성 메서드
    static void go(int idx, List<Integer> list) {
       // M개를 모두 골랐다면 치킨 거리 계산 후 최솟값 갱신
       if (list.size() == m) {
          ans = Math.min(ans, getChickenDist(list));
          return;
       }

       // idx부터 끝까지 순회하며 치킨집 선택
       for (int i = idx; i < chicken.size(); i++) {
          list.add(i); 
          go(i + 1, list);
          list.remove(list.size() - 1); // 백트래킹 (원상 복구)
       }
    }

    // 선택된 M개의 치킨집을 바탕으로 도시의 치킨 거리를 계산하는 메서드
    static int getChickenDist(List<Integer> list) {
       int ret = 0; // 도시의 치킨 거리 총합
       
       for (Node h : home) {
          int chickenDist = Integer.MAX_VALUE; // 현재 집의 치킨 거리

          for (int i : list) {
             Node c = chicken.get(i);
             // 맨해튼 거리 계산 공식 적용
             int d = Math.abs(h.y - c.y) + Math.abs(h.x - c.x);
             chickenDist = Math.min(chickenDist, d);
          }
          ret += chickenDist;
       }

       return ret;
    }

    // 좌표를 담기 위한 이너 클래스
    static class Node {
       int y, x;

       Node(int y, int x) {
          this.y = y;
          this.x = x;
       }
    }
}

알고리즘 분류

구현, 브루트포스 알고리즘 (완전탐색), 백트래킹 (Backtracking)