[Python/Java] 백준 15686 - 치킨 배달 [Brute Force]

문제

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

 

해설

각 치킨집의 조합을 만들어서 Brute Force를 이용하여 해결하였다.

 

백준이 지금 시간 기준으로 이상한건지는 모르겠지만 Python과 Java 코드 모두 제출하면 성공일 때도 있고 컴파일 에러나 런타임 에러(NZEC)가 발생할 때도 있다. 정답이었던 코드를 그대로 제출해도 이런 결과가 나와서 원인이 뭔지 찾지 못하였다. 혹시 비슷한 현상이 일어나거나 업로드한 코드에서 문제가 있는 부분을 알고 계신다면 댓글 부탁드립니다.

 

Python

from sys import stdin


def get_distance(combination: list):
    total_distance = 0

    for hx, hy in houses:
        min_distance = float('inf')
        for cx, cy in combination:
            min_distance = min(min_distance, abs(hx - cx) + abs(hy - cy))
        total_distance += min_distance
    return total_distance


def generate_combinations(arr, m, start, selected):
    if len(selected) == m:
        all_combinations.append(selected[:])  # 깊은 복사해서 저장
        return

    for i in range(start, len(arr)):
        selected.append(arr[i])
        generate_combinations(arr, m, i + 1, selected)
        selected.pop()  # 백트래킹 (원래 상태로 되돌리기)


n, m = map(int, stdin.readline().split(" "))
city = [list(map(int, stdin.readline().strip().split(" "))) for _ in range(n)]

houses = []
chickens = []
for r in range(n):
    for c in range(n):
        if city[r][c] == 1:
            houses.append((r, c))
        elif city[r][c] == 2:
            chickens.append((r, c))

all_combinations = []
generate_combinations(chickens, m, 0, [])

answer = float('inf')
for selected in all_combinations:
    answer = min(answer, get_distance(selected))
print(answer)

 

Java

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

public class Main {
    static int n, m;
    static List<int[]> houses = new ArrayList<>();
    static List<int[]> chickens = new ArrayList<>();
    static List<List<int[]>> allCombinations = new ArrayList<>();
    static int minCityDistance = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] condition = br.readLine().split(" ");
        n = Integer.parseInt(condition[0]);
        m = Integer.parseInt(condition[1]);

        for(int r = 0; r < n; r++) {
            String[] line = br.readLine().split(" ");
            for(int c = 0; c < n; c++) {
                int value = Integer.parseInt(line[c]);
                if (value == 1) houses.add(new int[]{r, c});
                else if (value == 2) chickens.add(new int[]{r, c});
            }
        }

        generateCombinations(0, new ArrayList<>());
        for(List<int[]> selected : allCombinations) {
            minCityDistance = Math.min(minCityDistance, getDistance(selected));
        }

        System.out.println(minCityDistance);
    }

    // 백트래킹을 이용한 조합 생성
    static void generateCombinations(int start, List<int[]> selected) {
        if(selected.size() == m) {
            allCombinations.add(new ArrayList<>(selected));
            return;
        }

        for(int i = start; i < chickens.size(); i++) {
            selected.add(chickens.get(i));
            generateCombinations(i + 1, selected);
            selected.remove(selected.size() - 1);  // 백트래킹
        }
    }

    static int getDistance(List<int[]> combination) {
        int totalDistance = 0;

        for(int[] house : houses) {
            int hx = house[0], hy = house[1];
            int minDistance = Integer.MAX_VALUE;

            for(int[] chicken : combination) {
                int cx = chicken[0], cy = chicken[1];
                minDistance = Math.min(minDistance, Math.abs(hx - cx) + Math.abs(hy - cy));
            }

            totalDistance += minDistance;
        }

        return totalDistance;
    }
}