백준 15686번 - 치킨 배달

https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

 

 

 

 

일년 전에 알고리즘 스터디할 때 풀어봤던 문제이다. 그때는 못 풀어서 해설을 참고해서 풀었는데, 이번에는 해설을 참고하지 않고 온전히 내 힘으로 풀었다. 실력이 는 거 같아서 뿌듯했다!

 

 

 

 

 

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다.

 

1. 배열의 정보를 입력받을 때, 치킨집의 좌표를 클래스로 생성된 객체의 리스트로 저장한다

2. 리스트에 저장된 치킨집 중 M개를 조합을 통해 뽑는다. 이때 0개부터 M개 조합 모두에 대해 조합을 실시한다.

3. 주어진 수만큼 다 뽑았으면, 선택된 치킨집의 정보를 바탕으로 치킨 거리를 구한다.

- 한 집에 대해 선택된 모든 치킨 집과의 거리를 구해 가장 가까운 치킨집 사이의 거리를 구한다.

- 모든 집의 치킨거리를 더한다

4. 최솟값을 값을 갱신한다.

 

 

 

 

 

생각해보니 조합 알고리즘에 visited 배열이 필요없다. 그래서 visited 체크를 할 필요가 없다. 하지만 방문한 곳의 인덱스를 저장하기 위한 정보로는 썼다.

 

 

 

 

 

코드

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

public class Main {
	static int N, M;
	static List<Dot> chickenList;
	static List<Dot> houseList;
	static boolean[] visited;
	static int min = Integer.MAX_VALUE;

	static class Dot {
		int x;
		int y;

		public Dot(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	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());

		chickenList = new ArrayList<>();
		houseList = new ArrayList<>();

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

			for (int j = 0; j < N; j++) {
				int value = Integer.parseInt(st.nextToken());

				if(value == 1) {
					houseList.add(new Dot(i, j));
				}else if(value == 2) {
					chickenList.add(new Dot(i, j));
				}
			}
		}

		// 구현
		visited = new boolean[chickenList.size()];

		for (int i = 1; i <= M; i++) { // 1, 2, .., M개 조합
			combination(0, 0, i);
		}

		// 출력
		System.out.println(min);
	}

	public static void combination(int start, int depth, int m) {
		if (depth == m) {
			min = Math.min(min, getDistance());
			return;
		}

		for(int i = start; i < chickenList.size(); i++) {
			if (visited[i]) continue;

			visited[i] = true;
			combination(i + 1, depth + 1, m);
			visited[i] = false;
		}
	}

	public static int getDistance() {
		int distanceSum = 0;
		
		for(Dot house : houseList) {
			int dMin = Integer.MAX_VALUE;
			
			for(int i = 0; i < chickenList.size(); i++) {
				if(visited[i]) { //살아남은 치킨집이면
					Dot chicken = chickenList.get(i);
					int d = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);
					dMin = Math.min(dMin, d);
				}
			}
			
			distanceSum += dMin;
		}
		
		return distanceSum;
	}
}

 

 

 

 

 

 

결과