1 분 소요

문제

문제 바로가기

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

  • 첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.

접근방법

백트래킹을 이용해서 탐색해야 하는 문제이다.

  • 전체 치킨집의 수(count)와 M을 이용해 폐업해야 하는 치킨집의 수(close)를 알아내고,

  • 재귀를 통해 전체 치킨집들이 close수만큼 폐업하는 모든 경우의 수를 찾아주었다.

  • 각 경우의 수에서 distance함수를 호출해서 모든 집들의 치킨거리를 구하는 방법을 반복해 최솟값을 반환했다.

풀이

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

class Coo {
    int x, y;
    Coo(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N, M;
    static int[][] map;
    static int count= 0, close;
    static int countHome = 0;
    static Coo[] chickens, homes;
    static int min = 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());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        chickens = new Coo[13];
        homes = new Coo[N*2];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(map[i][j] == 2) {
                    chickens[count] = new Coo(i, j);
                    count++;
                }
                else if(map[i][j] == 1) {
                    homes[countHome] = new Coo(i, j);
                    countHome++;
                }
            }
        }
        close = count - M;
        dfs(0, 0);
        System.out.println(min);
    }
    public static void dfs(int index, int depth) {
        if(depth == close) {
            int sum = 0;
            for(int i = 0; i < countHome; i++) {
                sum += distance(homes[i].x, homes[i].y);
            }
            min = Math.min(sum, min);
            return;
        }
        for(int i = index; i < count; i++) {
            map[chickens[i].x][chickens[i].y] = 0;
            dfs(i+1, depth+1);
            map[chickens[i].x][chickens[i].y] = 2;
        }
    }

    public static int distance(int x, int y) {
        int md = Integer.MAX_VALUE;
        for(int i = 0; i < count; i++) {
            int cx = chickens[i].x;
            int cy = chickens[i].y;
            if(map[cx][cy] == 2) {
                int distance = Math.abs(x-cx) + Math.abs(y-cy);
                md = Math.min(distance, md);
            }
        }
        return md;
    }
}

댓글남기기

참고