골드V 치킨 배달

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

15686번: 치킨 배달

기존 풀이에서는 백트래킹을 통해 각 치킨 집이 살아남는 모든 경우의 수를 2차원 배열에 반영하고

배열을 순회하면서 BFS를 사용하여 각 집에서 가장 가까운 치킨집과 그 거리를 구했습니다.

 

개선된 코드에서는 백트래킹으로 모든 경우의 수를 구하는 것은 같지만

N(집) 대 M(치킨집)으로 각 집과 치킨 집 사이의 거리를 모두 비교 후 최단 거리를 구했습니다.

기존 코드

개선 코드

// 기존 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    private static int result = (int)1e9;

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

        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);
        int[][] city = new int[N][N];
        ArrayList<int[]> chickens = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            String[] blocks = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                int blockNum = Integer.parseInt(blocks[j]);
                if (blockNum == 2) {
                    chickens.add(new int[] {i, j});
                }
                city[i][j] = blockNum;
            }
        }

        dfs(city, chickens, M, chickens.size(), -1);
        System.out.println(result);
    }

    private static void dfs(int[][] city, ArrayList<int[]> chickens, int M, int chickenCnt, int idx) {
        if (M >= chickenCnt) {
            int totalChickenDistance = calculateTotalChickenDistance(city);
            if (totalChickenDistance < result) {
                result = totalChickenDistance;
            }
            return;
        }

        for (int i = 0; i < chickens.size(); i++) {
            if (i <= idx) {
                continue;
            }
            int[] chicken = chickens.get(i);
            city[chicken[0]][chicken[1]] = 0;
            dfs(city, chickens, M, chickenCnt - 1, i);
            city[chicken[0]][chicken[1]] = 2;
        }

    }

    private static int calculateTotalChickenDistance(int[][] city) {
        int N = city.length;
        int totalChickenDistance = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int blockNum = city[i][j];
                if (blockNum == 1) {
                    totalChickenDistance += getNearestChickenDistance(city, i, j);
                }
            }
        }

        return totalChickenDistance;
    }

    private static int getNearestChickenDistance(int[][] city, int row, int col) {
        int[][] moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        boolean[][] visitMap = new boolean[city.length][city.length];

        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {row, col});

        while (!queue.isEmpty()) {
            int[] poll = queue.poll();
            int currentRow = poll[0];
            int currentCol = poll[1];
            if (city[currentRow][currentCol] == 2) {
                return getChickenDistance(row, col, currentRow, currentCol);
            }
            for (int[] move : moves) {
                int nextRow = currentRow + move[0];
                int nextCol = currentCol + move[1];
                if (!isInRange(city.length, nextRow, nextCol) || visitMap[nextRow][nextCol]) {
                    continue;
                }
                visitMap[nextRow][nextCol] = true;
                queue.add(new int[] {nextRow, nextCol});
            }
        }

        return 0;
    }

    private static boolean isInRange(int length, int row, int col) {
        return 0 <= row && row < length
                && 0 <= col && col < length;
    }

    private static int getChickenDistance(int homeRow, int homeCol, int chickenRow, int chickenCol) {
        return Math.abs(homeRow - chickenRow) + Math.abs(homeCol - chickenCol);
    }
}

// 개선 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.ArrayList;

public class Main {
    private int totalChickenDistance = (int)1e9;
    private final ArrayList<int[]> homes = new ArrayList<>();
    private final ArrayList<int[]> chickens = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] split = br.readLine().split(" ");

        int N = Integer.parseInt(split[0]);
        int M = Integer.parseInt(split[1]);

        for (int row = 0; row < N; row++) {
            String[] blocks = br.readLine().split(" ");
            for (int col = 0; col < N; col++) {
                int blockNum = Integer.parseInt(blocks[col]);
                int[] coordinate = {row, col};
                if (blockNum == 1) {
                    homes.add(coordinate);
                } else if (blockNum == 2) {
                    chickens.add(coordinate);
                }
            }
        }

        dfs(M, chickens.size(), -1);
        System.out.println(totalChickenDistance);
    }

    private void dfs(int M, int surviveChickenCnt, int idx) {
        if (M >= surviveChickenCnt) {
            updateTotalChickenDistance(homes, chickens);
            return;
        }

        for (int i = 0; i < chickens.size(); i++) {
            if (i <= idx) {
                continue;
            }
            int[] chicken = chickens.get(i);
            chickens.set(i, null);
            dfs(M, surviveChickenCnt - 1, i);
            chickens.set(i, chicken);
        }

    }

    private void updateTotalChickenDistance(ArrayList<int[]> homes, ArrayList<int[]> chickens) {
        int sum = 0;

        for (int[] home : homes) {
            int minDistance = (int)1e9;
            for (int[] chicken : chickens) {
                if (chicken == null) {
                    continue;
                }
                minDistance = Math.min(minDistance, getChickenDistance(home[0], home[1], chicken[0], chicken[1]));
            }
            sum += minDistance;
        }
        totalChickenDistance = Math.min(totalChickenDistance, sum);
    }

    private int getChickenDistance(int homeRow, int homeCol, int chickenRow, int chickenCol) {
        return Math.abs(homeRow - chickenRow) + Math.abs(homeCol - chickenCol);
    }
}