[백준 15686번] 치킨배달 [JAVA]

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

15686번: 치킨 배달

1. 문제설명

N * N 크기의 맵이 주어집니다. 해당 맵에 0은 빈공간 집은 1 치킨집은 2로 표현이 됩니다.

M은 폐업 시키지 않을 치킨 집이고 해당 집의 치킨거리는 해당 집 (r1, c1)과 치킨집 사이(r2, c2)의 거리를  |r1-r2| + |c1-c2| 로 계산하여 구합니다.

폐업 시킬 치킨집을 잘 골라서 해당 마을의 치킨거리를 최소로 만드는 것이 목표입니다.

 

2.풀이

처음에는 맵으로 접근을 해 bfs같은 탐색을 통해 거리를 구하려고 했습니다. 하지만 결국 필요한 것은 치킨집의 좌표와 집의 좌표인 것을 알았고 이를 임의의 좌표를 저장하는 클래스로 만들어 ArrayList에 저장하도록 했습니다.

 

중요한 것은 살아있는 치킨집과 집 사이의 치킨거리를 구하고 치킨거리합의 최소값을 구해야 합니다.

 

이를 위해서는 dfs 탐색을 기본으로 조건을 걸어 재귀를 풀어주는 백트래킹 알고리즘이 유효하다고 생각했습니다. 재귀 종료의 조건은 count가 M을 만족하는 경우이고 치킨거리의 합이 -99인 경우는 새로운 값을 넣어주고 그 외의 경우에는 기존 값과 비교하여 작은 값을 넣어줍니다.

 

탐색 같은 경우는 0부터 시작하여 치킨집 Array의 크기 - m 까지 진행하는데 무의미한 탐색을 방지하기 위함입니다.

 

이후 dfs를 돌리는데 다음 재귀 진행과정은 현재 index+1 부터 for문을 돌려 해당하는 치킨집의 정보를 현재 리스트에 넣고 재귀에 들어갑니다. 재귀를 탈출하는 경우 현재 리스트 가장 뒤에 값을 제거함으로써 다음 값을 넣어 탐색할 수 있도록 만들어 줍니다.

 

3.소스코드

//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    static ArrayList<pos> chicken = new ArrayList();
    static ArrayList<pos> currentList = new ArrayList();
    static int sum = -99;
    static int n;
    static int m;
    static ArrayList<pos> home = new ArrayList();

    public Main() {
    }

    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());

        int i;
        for(i = 0; i < n; ++i) {
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < n; ++j) {
                int check = Integer.parseInt(st.nextToken());
                if (check == 2) {
                    chicken.add(new pos(i, j));
                } else if (check == 1) {
                    home.add(new pos(i, j));
                }
            }
        }

        for(i = 0; i <= chicken.size() - m; ++i) {
            currentList.add((pos)chicken.get(i));
            dfs(i, 1);
            currentList.remove(currentList.size() - 1);
        }

        System.out.println(sum);
    }

    static void dfs(int index, int count) {
        if (count == m) {
            if (sum == -99) {
                sum = chickenSum();
            } else {
                sum = Math.min(sum, chickenSum());
            }

        } else {
            for(int i = index + 1; i < chicken.size(); ++i) {
                currentList.add((pos)chicken.get(i));
                dfs(i, count + 1);
                currentList.remove(currentList.size() - 1);
            }

        }
    }

    private static int chickenSum() {
        int sum = 0;

        for(int i = 0; i < home.size(); ++i) {
            int min = Math.abs(((pos)home.get(i)).x - ((pos)currentList.get(0)).x) + Math.abs(((pos)home.get(i)).y - ((pos)currentList.get(0)).y);

            for(int j = 1; j < currentList.size(); ++j) {
                min = Math.min(min, Math.abs(((pos)home.get(i)).x - ((pos)currentList.get(j)).x) + Math.abs(((pos)home.get(i)).y - ((pos)currentList.get(j)).y));
            }

            sum += min;
        }

        return sum;
    }

    static class pos {
        int x;
        int y;

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

5. 피드백

틀렸습니다 같은 경우 조건문 하나를 잘못수정해서 발생했지만, 아이디어 구상 및 구현까지 깔끔하게 해결되어 기분이 좋은 문제였습니다.