[백준] 15686 치킨배달

---

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

글 읽기 - [C++] 1%도 못가서 틀렸다고 나오네요.. 도와주세요!!

https://yabmoons.tistory.com/50

[ 백준 15686 ] 치킨배달 (C++)

 

---

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

public class Main {
	static int N;
	static int M;
	static int[][] xy;
	static boolean[][] chic;
	static int live_x[];
	static int live_y[];
	static int m_min = 9999;
	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());
	xy = new int[N][N];
	chic = new boolean[N][N];
	live_x = new int[M];
	live_y = new int[M];
	for(int i = 0; i < N; i++) {
		st = new StringTokenizer(br.readLine(), " ");
		for(int j = 0; j < N; j++) {
			xy[i][j] = Integer.parseInt(st.nextToken());
		}
	}
	dfs(0,0);
	System.out.println(m_min);
	}
	static void dfs(int idx, int count) {
		//좌표 2인걸 찾고 M만큼 찾으면 리턴
		if(count == M) {
			int ch_m = chicken();
			m_min = Math.min(m_min, ch_m);
			return;
		}
		for(int i = idx; i < N; i++) { //열
			for(int j = 0; j < N; j++) { //행
				if(xy[i][j] == 2) {
					if(!chic[i][j]) {
						chic[i][j] = true;
						live_x[count] = i;
						live_y[count] = j;
						dfs(i, count + 1);
						chic[i][j] = false;
					}
				}
			}
		}
	}
	static int chicken() {
		int min = 9999;
		int result = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				if(xy[i][j] == 1) {
					for(int ci = 0; ci < M; ci++) {
							min = Math.min(min ,Math.abs(i-live_x[ci]) + Math.abs(j-live_y[ci]));
					}
					result += min;
					min = 9999;
				}
			}
		}
		return result;
	}
}