[Gold V] 치킨 배달 - 15686

문제 링크

성능 요약

메모리: 20092 KB, 시간: 224 ms

분류

백트래킹, 브루트포스 알고리즘, 구현

제출 일자

2024년 8월 29일 17:41:06

문제 설명

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

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

<p>임의의 두 칸 (r₁, c₁)과 (r₂, c₂) 사이의 거리는 |r₁-r₂| + |c₁-c₂|로 구한다.</p>

<p>예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.</p>

<pre>0 2 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 2 </pre>

<p>0은 빈 칸, 1은 집, 2는 치킨집이다.</p>

<p>(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.</p>

<p>(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.</p>

<p>이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.</p>

<p>도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, <strong>도시의 치킨 거리</strong>가 가장 작게 될지 구하는 프로그램을 작성하시오.</p>

입력

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

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

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

출력

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

풀이

java코드 복사
import java.io.*;
import java.util.*;

public class Main {
	static int N, M;
	static int[][] map;
	static List<Node> house;
	static List<Node> chicken;
	static int answer;
	static boolean[] remaining;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		house = new ArrayList<>();
		chicken = new ArrayList<>();
		map = new int[N][N];

        for (int i=0; i<N; i++) { // map과 치킨집, 집의 리스트 저장
            st= new StringTokenizer(br.readLine(), " ");
			for (int j=0; j<N; j++) {
				map[i][j]= Integer.parseInt(st.nextToken());
				if (map[i][j]= 1) {
					house.add(new Node(i, j));
				}
				if (map[i][j]= 2) {
					chicken.add(new Node(i, j));
				}
			}
        }

		answer= Integer.MAX_VALUE;
		remaining= new boolean[chicken.size()];
		dfs(0, 0);
		bw.write(answer + "\n");
        br.close();
        bw.flush();
        bw.close();
    }

    // dfs
	public static void dfs(int start, int count){
		if (count= M) {
			int result= 0;
			for (int i=0; i<house.size(); i++) {
				int tmp= Integer.MAX_VALUE;
				for (int j=0; j<chicken.size(); j++) {
					if (remaining[j]) {
						int distance= Math.abs(house.get(i).x - chicken.get(j).x) 
						+ Math.abs(house.get(i).y - chicken.get(j).y);
						tmp= Math.min(tmp, distance);
					}
				}
				result = tmp;
			}
			answer= Math.min(answer, result);
			return;
		}

        // backtracking
		for (int i=start; i<chicken.size(); i++) {
			remaining[i]= true;
			dfs(i+1, count+1);
			remaining[i]= false;
		}
	}

}

// 노드
class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x= x;
		this.y= y;
	}
}