피자배달거리 (DFS 조합)

 

고찰.

 

1. 조합을 구하는 로직에서 DFS(int level, int start)의 역할을 파악하는 것 중요.

combi[level] = i;   

2. 조합을 구할 때, ArrayList의 인덱스를 저장하여 구현.

3. 실수한 점. (거리를 구하는 공식이 주어졌음에도 거리를 구하는데 DFS를 사용하려 함, 관성을 버리고 문제를 읽고 생각하는 연습 필요.)

4. 처음 문제 읽을 때, 6C4 = 15가지 경우라는 것을 생각하고 접근하면 분석이 쉬워짐.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Main {

	static int m, n, answer=Integer.MAX_VALUE;

	int[] dx = { 0, 0, 1, -1 };
	int[] dy = { 1, -1, 0, 0 };

	public static void main(String args[]) throws Exception {
		Main M = new Main();
		Scanner in = new Scanner(System.in);
		
		n = in.nextInt();
		m = in.nextInt();
		int [][]map = new int[n+1][n+1];
		ArrayList<Position> home = new ArrayList<>();
		ArrayList<Position> pizza = new ArrayList<>();
		
		for ( int i = 1; i <= n ; ++i) {
			for (int j = 1; j <=n; ++j) {
				map[i][j] = in.nextInt();
				if(map[i][j] == 2)
					pizza.add(M.new Position(i, j));
				else if (map[i][j]==1)
					home.add(M.new Position(i,j));
				else ;
			}
		}
		
		int []combi = new int[m];
		M.DFS_COMBI(0, 0 , combi, pizza , home);
		System.out.println(answer);
	}


	private  void DFS_COMBI(int level, int start, int []combi ,ArrayList<Position> pizza, ArrayList<Position> home) {
			if( level == m) {
				/*
				for(int idx : combi) {
					System.out.print(String.format("%d ",idx));
				}
				System.out.println();
				*/
				int sum = 0;
				for ( Position h : home ) {
					int dis = Integer.MAX_VALUE;
					for (int i : combi) {
						dis = Math.min(dis,  Math.abs( pizza.get(i).x - h.x ) + Math.abs( pizza.get(i).y - h.y ));
					}
					sum +=dis;
				}
				
				answer = Math.min(answer, sum);
				
			} else {
				for ( int i = start ; i < pizza.size(); i++) {
					combi[level] = i;
					DFS_COMBI(level+1, i+1,  combi, pizza, home);
				}
			}
		
	}


	class Position{
		int x,y;
		Position(int x , int y){
			this.x = x;
			this.y = y;
		}
	}
	
	


}


ex)
input 
4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2
output
6