[백준] 15686번 치킨 배달 - (JAVA)

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

15686번: 치킨 배달

 

간만에 검색 안 하고 풀었다ㅠㅠ

기쁘다ㅠㅠㅠㅠㅠ

이 다음 순열, 조합, 부분집합 다 정리해야겠다!!

 

집가서 정리해야지!><

 

---

풀이 핵심 키워드!

>>  조합  <<

 

Why?

N개의 치킨집이 주어졌을 때, R개의 치킨집을 살려놓는다.

선택된 R개의 치킨집 집합과 집들의 치킨거리가 최소인 경우의 치킨거리를 구한다!

 

 

조합은 어떻게 짜지?

=> Next Permutation을 이용한다!

 

---

 

단순 풀이과정

 

1) 입력받기

2) Next Permutation을 위한 배열 생성

3) Next Permutation을 실행하기

4) 각 실행마다 나온 결과값을 통해 최소 치킨 거리 구하기

 

---

 

1) 입력받기

	static int N, CUT; // 배열 크기, 허용된 치킨집 개수
	static int[] index;	// Next Permutation 결과 저장
	static Pos[] tgt;	// 해당되는 치킨집 위치저장
	// 치킨집, 마을 위치 저장용
	static class Pos {
		int x, y;
		public Pos() { }
		public Pos(int y, int x) {
			this.x = x;
			this.y = y;
		}
	}
	// 치킨집 좌표와 마을 좌표 저장
	static ArrayList<Pos> c = new ArrayList<>(), v = new ArrayList<>();

	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());
		CUT = Integer.parseInt(st.nextToken());
		tgt = new Pos[CUT];

		// 입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				// 마을과 치킨집을 구분해 저장
				if (temp == 1) v.add(new Pos(i, j));
				if (temp == 2) c.add(new Pos(i, j));
			}
		}
    }
}

나는  Pos 클래스를 이용해 각 건물의 x,y좌표를 따로 저장하였다.

ArrayList<Pos> C에는 치킨집들의 좌표를,

ArrayList<Pos> V에는 가정집들의 좌표를 저장했다.

 

tgt배열은 NextPermutation을 돈 후 선택된 치킨집들을 저장할 배열이다.

 

 

---

2) Next Permutation을 위한 배열 생성

 

 

Q. 왜 1로 채우나요?

Next Permutation 적용을 위해 

 

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

public class Main {
	static int N, CUT;
	static int[] index;	// Next Permutation 결과 저장
	static Pos[] tgt;	// 해당되는 치킨집 위치저장
	// 치킨집, 마을 위치 저장용
	static class Pos {
		int x, y;
		public Pos() { }
		public Pos(int y, int x) {
			this.x = x;
			this.y = y;
		}
	}
	// 치킨집 좌표와 마을 좌표 저장
	static ArrayList<Pos> c = new ArrayList<>(), v = new ArrayList<>();

	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());
		CUT = Integer.parseInt(st.nextToken());
		tgt = new Pos[CUT];

		// 입력
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int temp = Integer.parseInt(st.nextToken());
				// 마을과 치킨집을 구분해 저장
				if (temp == 1) v.add(new Pos(i, j));
				if (temp == 2) c.add(new Pos(i, j));
			}
		}
		
		// NP를 위한 index 초기화
		index = new int[c.size()];
		for (int i = 0; i < CUT; i++) {
			index[c.size() - i - 1] = 1;
		}

		// 최소 치킨거리 저장
		int solve = Integer.MAX_VALUE;
		while (true) {
			int tgtIdx = 0;
			// np결과에 해당되는 치킨집 tgt에 저장
			for (int i = 0; i < index.length; i++) {
				if (index[i] == 1) {
					tgt[tgtIdx++] = c.get(i);
				}
			}

			// 현 tgt에 대한 치킨거리
			int allSum = 0;
			for (int i = 0; i < v.size(); i++) {
				int min = Integer.MAX_VALUE;
				// 전체 치킨집과 집 간 치킨 거리 연산
				// 한 집에 대한 가장 작은 치킨 거리 도출
				for (int j = 0; j < tgt.length; j++) {
					int result = Math.abs(v.get(i).x - tgt[j].x) + Math.abs(v.get(i).y - tgt[j].y);
					if (min > result) min = result;
				}
				// 최소 치킨거리 합산
				allSum += min;
			}
			// 현재까지 tgt중 가장 낮은 치킨거리를 도출한 합산 도출
			if (solve > allSum) solve = allSum;
			// Next Permutation 종료조건
			if (!np(index)) break;
		}
		// 정답 출력
		System.out.println(solve);
	}
	// NextPermutation
	static boolean np(int array[]) {
		int i = array.length - 1;

		while (i > 0 && array[i - 1] >= array[i]) --i;

		if (i == 0)
			return false;

		int j = array.length - 1;
		while (array[i - 1] >= array[j]) --j;

		swap(array, i - 1, j);

		int k = array.length - 1;
		while (i < k) {
			swap(array, i++, k--);
		}
		return true;
	}
	// NP중 swap용
	static void swap(int[] array, int i, int j) {
		int temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
}