[조합] 백준 15686번 치킨 배달 - JAVA

 

골드 5 길래 얼른 풀고 시험공부 할라했더니

3시간 순삭했던 문제...;;

 

나의 실패썰과 성공썰을 공유하겠다.

 

 

---

1. 출처

---

 

 

처음엔 그냥 무작정 브루트포스 방식으로 알고리즘을 짰는데, 조합으로 풀지 않으면 답이 나오지 않겠다라는 생각을 하게 해 준 글이 있었다. 그래서 2번째 알고리즘은 조합으로 풀었더니 정답이 나왔다.

 

 

---

2. 설계 / 전체코드

---

1) 실패한 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

	static class Node {
		int r;
		int c;

		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}

	static class Store implements Comparable<Store> {
		int num;// 가게번호
		int popular;// 치킨집이 얼마나 유명한가? 각 치킨집은 몇 집이나 방문하는지
		int distance;// 각 치킨집마다 모든 집에서의 거리가 몇인가?

		public Store(int num, int popular, int distance) {
			super();
			this.num = num;
			this.popular = popular;
			this.distance = distance;
		}

		public Store(int num, int distance) {
			super();
			this.num = num;
			this.popular = popular;
			this.distance = distance;
		}

		@Override
		public int compareTo(Store o) {
			// 가장 많은 집이 방문하는 치킨집 중 모든 집의 거리가 가장 짧은 가게 선정
			if (this.popular == o.popular)
				return this.distance > o.distance ? 1 : -1;
			return this.popular < o.popular ? 1 : -1;
		}

	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt(); // 마을 크기
		int M = sc.nextInt();// 최대 선택할 치킨집 수

		List<Node> house = new ArrayList<>();// 집 위치 저장
		List<Node> store = new ArrayList<>();// 치킨집 위치 저장

		int[][] 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] == 1)
					house.add(new Node(i, j));
				if (map[i][j] == 2)
					store.add(new Node(i, j));
			}
		}

		// 입력 끝

		int[] popular = new int[store.size() + 1];// 치킨집이 얼마나 유명한가? 각 치킨집은 몇 집이나 방문하는지
		int[] distance = new int[store.size() + 1];// 각 치킨집마다 모든 집에서의 거리가 몇인가?

		PriorityQueue<Store>[] pick = new PriorityQueue[house.size()+1];// 각 집이 가장 가깝다고 생각하는 가게(가게 거리를 넣어서 가장 작은 순으로 배정)
		for (int i = 0; i <= house.size(); i++) {
			pick[i] = new PriorityQueue<>();
		}

		// 집하나 선택해서 전체 치킨집 체크
		for (int i = 0; i < house.size(); i++) {
			int minDistance = Integer.MAX_VALUE;
			int minDStore = 0;// 가장 가까운 거리의 치킨집 인덱스번호
			for (int j = 0; j < store.size(); j++) {

				int d = Math.abs(house.get(i).r - store.get(j).r) + Math.abs(house.get(i).c - store.get(j).c);

				distance[j + 1] += d;// 각 집 별 치킨집 거리 추가
				pick[i + 1].add(new Store(j + 1, d));

				// 치킨집 중 가장 가까운 치킨집 선정중
				if (d < minDistance) {
					minDistance = d;
					minDStore = j + 1;
				}

			}
			popular[minDStore]++;// 가장 가까운 치킨집에 단골 고객 추가

		}

		PriorityQueue<Store> result = new PriorityQueue<>();
		for (int j = 1; j <= store.size(); j++) {
			result.add(new Store(j, popular[j], distance[j]));
		}

		// 가장 많은 집이 방문하는 치킨집 중 모든 집의 거리가 가장 짧은 가게 선정 => M개
		int[] resultStore = new int[M];
		for (int i = 0; i < M; i++) {
			resultStore[i] = result.poll().num;
		}

		// 선정된 치킨집에 집 할당
		int resultD = 0;
		for (int i = 1; i <= house.size(); i++) {
			wish: while (!pick[i].isEmpty()) {
				Store cur = pick[i].poll();// 현재 집이 원하는 가게
				for (int j = 0; j < M; j++) {// 뽑힌 가게 만큼 돌아감
					if (cur.num == resultStore[j]) {// 원하는 가게가 뽑혔는지
						resultD += cur.distance;
						break wish;// 해당 집이 원하는 가게가 있으므로 다음 집 조사
					}
				}
			}
		}

		System.out.println(resultD);

	}
}

처음 문제를 봤을 땐 쉬웠는데, 예제를 해석하는 것이 어려웠다.

그래서 처음에는 어떻게 해석했냐면,

1) 한 가게에 몇 집이 가는지를 체크하고, 가장 인기있는 집 중

2) 모든 집이 가는 거리가 가장 작은 치킨집 선택

3) 치킨집 M개 선정 후 고객(집)을 가장 가까운 거리의 치킨집으로 배정

 

이라고 해석했다.

 

위 코드는 예제는 모두 정답으로 나온다. 근데 칼 오답이 나온다 ㅎㅎ;;;

그래서 왜 틀린 건지 분석하면서, 이해가 잘 안갔는데, 이런 반례가 눈에 들어왔다. 

 

https://www.acmicpc.net/board/view/95024

글 읽기 - TC는 맞는데 칼오답인 분들을 위한 약간의 팁

 

[반례]

5 1
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2

ans: 12



5 4
2 1 0 1 2
0 0 0 0 0
0 0 2 0 0
0 0 0 0 0
2 1 0 1 2

ans: 4

 

치킨집 1개를 선택할 때는 1번 테스트케이스에서는 가운데 치킨집을 선택하는 것이 모든 집에게 가까운 치킨집을 선택하는 방법이다. 하지만 2번 테스트케이스는 4개의 치킨집을 선택하는 것이기 때문에 각 집에서 가장 가까운 치킨집이 바로 옆 치킨집이기 때문에 가운데 있는 치킨집은 아웃이 되는 것이다.

 

근데 내 코드는 2번 테스트케이스는 잘 동작하는데, 1번 테스트케이스에서는 멍청해진다.

코드야 미안해...

 

그리고 저 반례를 보는 순간 왜 많은 사람들이 조합으로 풀었는지 이해가 갔다.

치킨집의 M개의 조합을 먼저 뽑고, 각 집은 어떤 치킨집이 가장 가까운 치킨집인지 최소 거리를 계산하는 것이다.

그리고 전체 조합 중 가장 가까운 M개의 치킨집 조합을 찾는 것이 관건인 문제였다. 

그 코드가 바로 아래 코드이다.

 

 

2) 성공한 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	static int N,M;
	static List<Node> house;
	static List<Node> store;
	static int[][] map;
	static int[] choice;
	static int result=Integer.MAX_VALUE;
	
	static class Node {
		int r;
		int c;

		public Node(int r, int c) {
			super();
			this.r = r;
			this.c = c;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt(); // 마을 크기
		M = sc.nextInt();// 최대 선택할 치킨집 수
		
		//초기화
		house = new ArrayList<>();// 집 위치 저장
		store = new ArrayList<>();// 치킨집 위치 저장
		choice = new int[M];//내가 선택할 M개의 치킨집
		
		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] == 1)
					house.add(new Node(i, j));
				if (map[i][j] == 2)
					store.add(new Node(i, j));
			}
		}

		// 입력 끝
		
		combination(0,1);
		
		System.out.println(result);

	}
	
	//depth (0~M-1) : 최대 M-1 깊이까지 가능 (M개의 치킨집을 뽑는거니까)
	//sel(1~store.size()) : store.size()만큼의 치킨집이 있는데 이 중 몇 번째 치킨 집을 뽑을 것이냐. store.size() 크기를 넘어가면 안됨
	public static void combination(int depth,int sel) {
		
		if(depth==M) {
			//M개의 치킨집 선택을 했다. -> 각 집이 어떤 치킨집을 선택할건지 거리 계산하여 가장 작은 거리 pick!
			//모든 집의 가장작은거리는 한 변수에 전체 더한다. 모든 조합 중 가장 작은 거리를 도출하면 된다.
			int sum=0;
			for(int i=0;i<house.size();i++) {//집의 수(0번부터 시작)
				int minDistance = Integer.MAX_VALUE;
				Node curH = house.get(i);//현재 집

				for(int j=0;j<M;j++) {//선택한 가게 수 (M고정)
					Node curS = store.get(choice[j]-1);//store는 0부터 시작하고, choice의 값은 1부터 시작해서 -1해줘야함
					
					int d = Math.abs(curH.r-curS.r)+ Math.abs(curH.c-curS.c);//거리 계산
					
					minDistance=Math.min(minDistance, d);//한 집에서 치킨집까지의 거리
					
				}
				sum+=minDistance;//각 집의 가장 가까운 치킨집 거리 더해주기
			}
			
			result = Math.min(result,sum);
			return;
		}
		
		if(sel==store.size()+1) {
			//치킨집 가게 수를 넘어섰다. 다 보았다.
			return;
		}
		
		choice[depth]=sel;
		combination(depth+1,sel+1);//치킨집 선택
		combination(depth,sel+1);//치킨집 선택안함
		
		
	}

}

오랜만에 조합 문제를 풀면서 공부까지 되었다.

정말 유익했던 문제다.