백준 15686번 치킨 배달 :: 마이구미

이 글은 백준 알고리즘 문제 15686번 "치킨 배달" 을 풀이한다.

2018 삼성 SW 역량 테스트 문제이다.

접근 방법은 브루트포스와 DFS 를 통해 풀이한다.

문제 링크 - https://www.acmicpc.net/problem/15686

DFS - http://mygumi.tistory.com/102

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

치킨집을 최대 M개 골랐을 때, 도시의 치킨 거리의 최소값을 구하는 문제가 된다.

이 때 최대 M개는 최대이기 때문에 쉽게 M개라고 고려하면 된다.

즉, 치킨집을 M개 고를 수 있는 모든 경우를 기준으로 도시의 치킨 거리를 구하면 된다.

모든 경우는 DFS 처럼 재귀적으로 탐색할 수 있다.

탐색하면서 M개의 경우가 나온다면, 거리를 구하면 된다.

이러한 탐색 문제가 익숙하다면, 쉽게 해결할 수 있다.

public static void search(int next, int cnt, int[][] prev) {
    int len = list.size(); 
    for (int i = next; i < len; i++) {
        int[][] dist = new int[n + 1][n + 1];
        for (int k = 1; k <= n; k++) {
            dist[k] = Arrays.copyOf(prev[k], n + 1);
        }
        Node node = list.get(i);
        int x = node.x;
        int y = node.y;

        // 치킨 거리 업데이트 && 도시 치킨 거리 반환 
        int sum = totalDistance(x, y, dist);
        if (cnt + 1 == k) {
            if (sum < min) {
                min = sum;
            }
        } else {
            search(i + 1, cnt + 1, dist);
        }
    }
}

list 는 치킨집들의 목록이다.

각 치킨집을 기준으로 모든 집 사이의 거리를 구한다.

M개의 치킨집의 경우가 완성되면, 도시의 치킨 거리를 구하거나 더 짧은 거리가 존재할 수 있기에 업데이트한다.

다른 출제 문제 15683번 "감시" 문제도 이와 같이 해결할 수 있다. (http://mygumi.tistory.com/313)

Github -https://github.com/hotehrud/acmicpc/blob/master/SAMSUMG/15686.java

static int n, k, min = Integer.MAX_VALUE;
static int[][] map;
static ArrayList<Node> list = new ArrayList<Node>();
 
private void solve() {
    n = sc.nextInt();
    k = sc.nextInt();
    map = new int[n + 1][n + 1];
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            map[i][j] = sc.nextInt();
            if (map[i][j] == 2) {
                list.add(new Node(j, i));
            }
        }
    }
 
    int[][] dist = new int[n + 1][n + 1];
    for (int k = 1; k <= n; k++) {
        Arrays.fill(dist[k], 9999);
    }
    search(0, 0, dist);
    System.out.println(min);
}
 
public static void search(int next, int cnt, int[][] prev) {
    int len = list.size();
    for (int i = next; i < len; i++) {
        int[][] dist = new int[n + 1][n + 1];
        for (int k = 1; k <= n; k++) {
            dist[k] = Arrays.copyOf(prev[k], n + 1); // deep copy
        }
        Node node = list.get(i);
        int x = node.x;
        int y = node.y;
 
        // 치킨 거리 업데이트 && 도시 치킨 거리 반환 
        int sum = totalDistance(x, y, dist);
        if (cnt + 1 == k) {
            if (sum < min) {
                min = sum;
            }
        } else {
            search(i + 1, cnt + 1, dist);
        }
    }
}
 
public static int totalDistance(int x, int y, int[][] dist) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (map[i][j] == 1) {
                int d = Math.abs(y - i) + Math.abs(x - j);
                if (dist[i][j] > d) {
                    dist[i][j] = d;
                }
                sum += dist[i][j];
            }
        }
    }
    return sum;
}
 
static class Node {
    int x;
    int y;
 
    Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}