본문 바로가기
Language/Java

[백준 | Java] 15686번 치킨 배달

by ㅇ달빛천사ㅇ 2025. 2. 7.
728x90
15686번 / 치킨 배달

❓ 치킨 배달

🏷️ 관련 주제 : Brute Force

 

💦 나의 시도

완전 탐색을 통한 최소 치킨 거리 구하기

도시의 크기 : N × N
폐업 시키지 않을 최대 치킨 집 개수 : M
2 ≤ N ≤ 50
1 ≤ M ≤ 13
(집의 개수) ≤ 2N
M ≤ (치킨 집 개수) ≤ 13

 

  1. BufferedReader를 통해 집의 위치와 치킨집의 위치를 입력 받아 int[] 배열로 ArrayList<int[]>에 담기
    • 0 : empty
    • 1 : 집
      • ArrayList<in[]> houses에 위치 인덱스를 담은 길이 2인 int[] 배열 추가
    • 2 : 치킨집
      • ArrayList<in[]> chickens에 위치 인덱스를 담은 길이 2인 int[] 배열 추가
  2. 2중 for문을 돌며 각 치킨집에 대한 모든 집의 치킨 거리를 int[] 배열에 담아 Map에 저장
    • ArrayList<int[]> chickens의 i번 인덱스 치킨집 위치를 꺼내 int[] chicken에 할당
    • 0 ~ houses.size() - 1 범위를 반복문으로 돌며 chicken에 대한 모든 집의 치킨 거리를 구해 int[] dis에 할당
      • ArrayList<int[]> houses의 j번 인덱스 치킨집 위치를 꺼내 int[] house에 할당
      • chicken에 대한 house의 치킨 거리를 구해 dis[j]에 할당
    • 인스턴스 변수 Map<Integer, int[]> distances에 치킨집 인덱스와 모든 집의 치킨 거리를 담은 배열 추가
      • 키 : i (= chickens에서 chicken이 위치한 인덱스)
      • 값 : dis (= chicken에 대한 모든 집의 치킨 거리를 담은 int[] 배열, 길이는 모든 집의 수와 일치)
  3. DFS로 치킨집을 하나씩 추가하며 완전 탐색으로 도시의 최소 치킨 거리 구하기
    • int[] keep에 남길 치킨집을 체크하며 최대 개수가 M 이하인 경우만 탐색

❌ 틀렸습니다.

DFS 함수에서 현재 인덱스의 치킨집의 도시 치킨 거리를 int[] curChickenDis에 가져와 할당하였는데
탐색 후, 변경된 도시의 치킨 거리를 해당 배열에 할당하면서
다음 탐색 시, 치킨집에 대한 도시의 치킨 거리가 아닌 탐색 결과 수정된 도시의 치킨 거리 배열이 조회되어 틀림

 

해당 부분을 int[] chickenDisI에 할당하고 in[] curChickenDis에 전체 남겨진 치킨집에 대한 도시의 치킨 거리를 배열로 할당하여 문제 해결



📑제출 기록 및 오답 원인

처음 제출의 오답 원인을 찾지 못한 상태에서 코드를 다시 작성하여 제출 성공하였으나
오답의 원인을 찾기 위해 다시 제출 시도하였습니다.
몇차례의 제출 이후 오답의 원인을 찾아 최종적으로 ArrayList<in[]> chickens의 치킨집을 clone()하여 사용하였습니다.

💯 해결 방법

1차 제출

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static int M;
    public static Map<Integer, int[]> distances = new HashMap<>();
    public static int minDis = 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());
        int N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ArrayList<int[]> chickens = new ArrayList<>();
        ArrayList<int[]> houses = new ArrayList<>();

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

            for (int j = 0; j < N; j++) {
                int type = Integer.parseInt(st.nextToken());
                int[] idx = {i, j};
                switch (type) {
                    case 1:
                        houses.add(idx);
                        break;
                    case 2:
                        chickens.add(idx);
                        break;
                    default:
                        break;
                }
            }
        }

        int chickensSize = chickens.size();
        int housesSize = houses.size();

        for (int i = 0; i < chickensSize; i++) {
            int[] chicken = chickens.get(i);
            int[] dis = new int[housesSize];

            for (int j = 0; j < housesSize; j++) {
                int[] house = houses.get(j);
                dis[j] = Math.abs(chicken[0] - house[0]) + Math.abs(chicken[1] - house[1]);
            }

            distances.put(i, dis);
        }

        int[] keep = new int[chickensSize];

        for (int i = 0; i < chickensSize; i++) {
            dfs(keep, distances.get(i), i, 0);
        }

        System.out.println(minDis);
    }

    public static void dfs (int[] keep, int[] preChickenDis, int keepIdx, int cnt) {
        cnt++;
        keep[keepIdx] = 1;

        int[] chickenDisI = distances.get(keepIdx);
        int[] curChickenDis = IntStream.range(0, chickenDisI.length).map(i -> Math.min(preChickenDis[i], chickenDisI[i])).toArray();
        int sumDis = Arrays.stream(curChickenDis).sum();
        minDis = Math.min(sumDis, minDis);

        if (cnt < M) {
            for (int i = keepIdx + 1; i < distances.size(); i++) {
                int[] curKeep = keep.clone();
                dfs(curKeep, curChickenDis, i, cnt);
            }
        }
    }
}

 

2차 제출

IntStream을 이용

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {
    public static int M;
    public static Map<Integer, int[]> distances = new HashMap<>();
    public static int minDis = 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());
        int N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ArrayList<int[]> chickens = new ArrayList<>();
        ArrayList<int[]> houses = new ArrayList<>();

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

            for (int j = 0; j < N; j++) {
                int type = Integer.parseInt(st.nextToken());
                int[] idx = {i, j};
                switch (type) {
                    case 1:
                        houses.add(idx);
                        break;
                    case 2:
                        chickens.add(idx);
                        break;
                    default:
                        break;
                }
            }
        }

        int chickensSize = chickens.size();
        int housesSize = houses.size();

        for (int i = 0; i < chickensSize; i++) {
            int[] chicken = chickens.get(i);
            int[] dis = new int[housesSize];

            for (int j = 0; j < housesSize; j++) {
                int[] house = houses.get(j);
                dis[j] = Math.abs(chicken[0] - house[0]) + Math.abs(chicken[1] - house[1]);
            }

            distances.put(i, dis);
        }

        IntStream.range(0, chickensSize).forEach(i -> dfs(new int[chickensSize], distances.get(i), i, 0));

        System.out.println(minDis);
    }

    public static void dfs (int[] keep, int[] preChickenDis, int keepIdx, int cnt) {
        cnt++;

        if (cnt > M) {
            return;
        }

        keep[keepIdx] = 1;

        int[] chickenDisI = distances.get(keepIdx);
        int[] curChickenDis = IntStream.range(0, preChickenDis.length).map(i -> Math.min(preChickenDis[i], chickenDisI[i])).toArray();
        int sumDis = Arrays.stream(curChickenDis).sum();
        minDis = Math.min(sumDis, minDis);

        final int finalCnt = cnt;
        IntStream.range(keepIdx + 1, distances.size()).forEach(i -> dfs(keep.clone(), curChickenDis, i, finalCnt));
    }
}

3차 제출

문제의 원인이었던 curChickenDis를 chickens.get(i).clone()으로 수정하여 할당 후 해결

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

public class Main {
    public static int M;
    public static Map<Integer, int[]> distances = new HashMap<>();
    public static int minDis = 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());
        int N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        ArrayList<int[]> chickens = new ArrayList<>();
        ArrayList<int[]> houses = new ArrayList<>();

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

            for (int j = 0; j < N; j++) {
                int type = Integer.parseInt(st.nextToken());
                int[] idx = {i, j};
                switch (type) {
                    case 1:
                        houses.add(idx);
                        break;
                    case 2:
                        chickens.add(idx);
                        break;
                    default:
                        break;
                }
            }
        }

        int chickensSize = chickens.size();
        int housesSize = houses.size();

        for (int i = 0; i < chickensSize; i++) {
            int[] chicken = chickens.get(i);
            int[] dis = new int[housesSize];

            for (int j = 0; j < housesSize; j++) {
                int[] house = houses.get(j);
                dis[j] = Math.abs(chicken[0] - house[0]) + Math.abs(chicken[1] - house[1]);
            }

            distances.put(i, dis);
        }

        int[] keep = new int[chickensSize];

        for (int i = 0; i < chickensSize; i++) {
            dfs(keep, distances.get(i), i, 0);
        }

        System.out.println(minDis);
    }

    public static void dfs (int[] keep, int[] preChickenDis, int keepIdx, int cnt) {
        cnt++;

        if (cnt > M) {
            return;
        }

        keep = keep.clone();
        keep[keepIdx] = 1;

        int[] curChickenDis = distances.get(keepIdx).clone();
        int sumDis = 0;

        for (int i = 0; i < curChickenDis.length; i++) {
            curChickenDis[i] = Math.min(preChickenDis[i], curChickenDis[i]);
            sumDis += curChickenDis[i];
        }

        if (sumDis < minDis) {
            minDis = sumDis;
        }

        for (int i = keepIdx + 1; i < distances.size(); i++) {
            int[] curKeep = keep.clone();
            dfs(curKeep, curChickenDis, i, cnt);
        }

    }
}
728x90
저작자표시 비영리 변경금지 (새창열림)

관련글

⇧
Top

티스토리툴바