백준 15686번 : 치킨배달 자바

🧫 문제 분석

 

✔️ 출처

치킨배달 골드 5

 

📖 문제

 

// 치킨 거리 = 집과 가장 까가운 치킨집 사이의 거리
// 집 기준, 집은 치킨거리를 가짐
// 도시의 치킨 거리 = 모든 집의 치킨 거리의 합
// 임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|

// 0 빈칸 , 1 집 , 2 치킨 집
// 집의 개수 <= 2N , 적어도 1개는 존재
// M <= 치킨집의 개수 <= 13

 

치킨 집 중 M개를 골라야하기에 백트래킹이 필요하다. 

중요한 것은 전체 치킨 집 수 중 M개를 뽑는 방법이다. 

 

처음에 그냥 i = 0 으로 모든 치킨집을 순회하면서 조합을 만들어갔기에 시간초과로 실패했다.

중요한 것은 m개의 치킨집을 효율적으로 뽑아서 치킨거리를 계산하는 것이다. 

치킨집을 뽑을때 이전에 뽑았던 가게는 이미 뽑혔기에 굳이 또 방문할 필요없다. 

따라서 +1을 해주어서 그다음 가게부터 순회하도록한다. 

---

🔅 문제 풀이

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

public class Main {
    static class Location {
        int r, c;

        public Location(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    static int m; // 치킨 집 개수
    static int chickenStreet = Integer.MAX_VALUE;
    static boolean[] visited;
    static ArrayList<Location> house = new ArrayList<>();
    static ArrayList<Location> 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());
        int n = Integer.parseInt(st.nextToken()); // 크기 n x n
        m = Integer.parseInt(st.nextToken());

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

            for (int j = 1; j <= n; j++) {
                String info = st.nextToken();
                if (info.equals("1")) {
                    house.add(new Location(i, j));

                } else if (info.equals("2")) {
                    chicken.add(new Location(i, j));
                }
            }
        }

        visited = new boolean[chicken.size()];
        recursion(0, 0);

        bw.write(chickenStreet + "\n");
        bw.flush();
        bw.close();
    }
    
	// 치킨 가게 중 m 개를 뽑는다. 
    private static void recursion(int depth, int start) {
       // m개가 뽑히면 도시의 치킨거리 최솟값을 구한다. 
        if (depth == m) {
            int tmp = clacMin();
            chickenStreet = Math.min(tmp, chickenStreet);
            return;
        }

        for (int i = start; i < chicken.size(); i++) {
            if (!visited[i]) {
                visited[i] = true;
                recursion(depth + 1,i + 1); // 조합을 효율적으로 나누는 방법
                visited[i] = false;
            }
        }
    }

    // 각 집마다 m개로 뽑힌 치킨가게와의 최소 거리 구하기
    private static int clacMin() {
        int tmp = 0;
        for (int i = 0; i < house.size(); i++) {
            int min = Integer.MAX_VALUE;
            Location home = house.get(i);

            for (int j = 0; j < chicken.size(); j++) {
                if (visited[j]) {
                    Location chick = chicken.get(j);
                    int street = Math.abs(home.r - chick.r) + Math.abs(home.c - chick.c);
                    if (street < min)
                        min = street;
                }
            }
            tmp += min;
        }
        return tmp;
    }
}

 

 

 

❗ 오답노트 / 필요한 지식

1. start 부터 시작하면서 i+1을 넘겨주는 방법을 몰라서 계속 시간초과가 떴다. 사실 엄청 당연한 건데 많이 반성하게 된다. 시간복잡도를 생각하고 효율적으로 짜보자..