공부 기록

import java.util.*;

public class Main {
	public static final int[] dr = { -1, 0, 0, 1 };
	public static final int[] dc = { 0, -1, 1, 0 };

	public static final int SPACE = 0;
	public static final int HOME = 1;
	public static final int CHICKEN = 2;

	public static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int chickenNum = in.nextInt();

		int mat[][] = new int[size][size];
		ArrayList<Point> chickens = new ArrayList<Point>();
		ArrayList<Point> homes = new ArrayList<Point>();

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				int position = in.nextInt();

				if (position == CHICKEN) {
					chickens.add(new Point(i, j));
				} else if (position == HOME) {
					homes.add(new Point(i, j));
				}
			}
		}

		for (int i = 0; i < chickens.size(); i++) {
			boolean check[] = new boolean[chickens.size()];
			check[i] = true;
			findAll(mat, homes, chickens, i, 1, chickenNum, check);
		}

		System.out.println(min);
	}

	public static void findAll(int mat[][], ArrayList<Point> homes, ArrayList<Point> chickens, int index, int num,
			int chickenNum, boolean[] check) {
		if (num == chickenNum) {
			min = Math.min(min, calcChickenDistance(mat, homes, chickens, check));
			return;
		}
		if (index == chickens.size()) {
			return;
		}

		for (int i = index + 1; i < chickens.size(); i++) {
			check[i] = true;
			findAll(mat, homes, chickens, i, num + 1, chickenNum, check);
			check[i] = false;
		}
	}

	public static int calcChickenDistance(int mat[][], ArrayList<Point> homes, ArrayList<Point> chickens,
			boolean[] check) {
		int distanceSum = 0;
		for (Point home : homes) {
			int distance = Integer.MAX_VALUE;
			for (int i = 0; i < check.length; i++) {
				if (check[i]) {
					Point chicken = chickens.get(i);
					distance = Math.min(distance, Math.abs(home.row - chicken.row) + Math.abs(home.col - chicken.col));
				}
			}
			distanceSum += distance;
		}

		return distanceSum;
	}
}

class Point {
	int row;
	int col;

	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

어차피 모든 경우의 수를 구하긴 해야한다.

하지만, 팰린드롬임을 한번 체크했다면 계속 그 글자가 팰린드롬인지 체크를 하지 않도록 어딘가 저장하는 방법은 없을지? => DP

팰린드롬 s의 서브스트링 s.substring(1, n-1) 또한 팰린드롬임을 이용하자.

=> DP[indexStart][indexEnd]: s.substring(indexStart, indexEnd)의 팰린드롬 여부

맨 첫 글자와 끝 글자가 같은 경우 중에서 팰린드롬이 될 수 있는 경우

1. 맨첫글자 위치 == 끝글자 위치 ex) "a"

2. 두 글자가 연속인 경우 ex) "aa"

3. 중간에 한 글자가 껴있는 경우 ex) "aba"

4. s.substring(첫 글자의 다음 글자, 끝 글자의 이전 글자)가 팰린드롬인 경우

import java.util.*;
class Solution {
	public List<List<String>> partition(String s) {
		List<List<String>> answer = new ArrayList<List<String>>();

		int length = s.length();
		boolean[][] dp = new boolean[length][length];

		palindrome(s, 0, answer, new Stack<String>(), dp);

		return answer;
	}

	public void palindrome(String s, int indexStart, List<List<String>> answer, Stack<String> currentList, boolean[][] dp) {
		if (indexStart >= s.length()) {
			answer.add(new ArrayList<>(currentList));
			return;
		}

		for (int end = indexStart; end < s.length(); end++) {
			if (s.charAt(indexStart) == s.charAt(end)) {
				if (end - 1 <= indexStart + 1 || dp[indexStart + 1][end - 1]) {
					dp[indexStart][end] = true;
					currentList.add(s.substring(indexStart, end + 1));
					palindrome(s, end + 1, answer, currentList, dp);
					currentList.pop();
				}
			}
		}
	}
}