[BOJ 15686] 치킨 배달

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

15686번: 치킨 배달

 

처음으로 1시간 내에 문제를 풀어봤다 ㅠ0ㅠ

 

삼성에 여러번 기출로 등장한 DFS 문제라서 쉽게 풀 수 있었다.

문제 분류는 브루트 포스로 DFS 혹은 BFS(가능한가?) 로 풀 수 있으며 DFS로 접근했다

 

풀이는 다음과 같은 방식으로 진행했다.

 

1. 전체 지도의 배열을 입력받으며 집의 위치(hx, hy)와 치킨집의 위치(mx, my)를 각각 저장한다. 지도에서 왼쪽 최상단에 있는 집에서부터 0, 1, 2, 3... 치킨집에서부터 0, 1, 2, 3... 순서로 번호를 매긴다고 생각했다.

 

2. dist라는 2차원 배열을 만들어 i(0~집 개수 - 1)번째 집에서 j(0 ~ 치킨집 개수 - 1)번째 치킨집까지의 거리를 저장한다

 

3. DFS를 돌린다

3-1. i번째 치킨집을 살릴지 말지를 선택하고, DFS를 돌린다. 

3-2. 이렇게 M개의 치킨집이 선택되었다면, dist배열에서 집과 선택된 치킨집들의 거리 중 최솟값을 구한다.

3-3. 그 최솟값들을 모두 더해서 리턴

 

여기에서 3-1의 구현을 잘 해야 한다.

만약에 첫 번째 재귀에서 0번째 치킨집을 살리기로 결정했다면, 두 번째 재귀에서는 1~부터 살릴지 말지를 결정해야 함

첫번째 재귀에서 k번째 치킨집을 살리기로 결정했다면, 두 번째 재귀에서는 k + 1부터 결정해야 한다(왜냐하면 0부터 k까지의 치킨집은 상위 단계에서 이미 결정이 되었기 때문)

 

(처음에 이 조건을 신경쓰지 않고 dfs에서의 for문을 무조건 0부터 시작하고, 반복문 내부에서 if(v[i] == 1) 조건을 걸어주었더니 시간초과가 발생했었다)

 

전반적으로 '스타트와 링크' 문제와 유사한 문제

public static int dfs(int cnt, int start, int cand_num){ // 인자 순서대로 몇번째 재귀인지, 몇번째 치킨집부터 보면 되는지, 치킨집 전체 수는 몇개인지
		if(cnt == M + 1){ // 치킨집 선택이 끝났다면
			int tdist = 0; // total distance
			int tmp = 0;
			int min;
			for(int i = 0 ; i < dist.length ; i++){ // i번째 집
				min = Integer.MAX_VALUE;
				for(int j = 0 ; j < dist[0].length ; j++){//j번째 치킨집
					if(v[j] == 1){ // 1이면 선택받은 치킨집
						tmp = dist[i][j];
						if(tmp < min && tmp != 0) min = tmp;
					}
				}
				tdist += min;
			}
			
			return tdist; 
		}

		int min = Integer.MAX_VALUE;
		int tmp = 0;
		for(int i = start ; i < cand_num ; i++){ // i번째 치킨집 유지
			v[i] = 1; // 선택했으므로 체크
			tmp = dfs(cnt+1, i + 1 , cand_num);
			v[i] = 0; // 재귀가 끝나면 해제해 주어야 한다
			if(tmp < min) { min = tmp; }
		}
		
		return min;
	}

 

전체 코드는 다음과 같다.

import java.util.*;

public class Num15685 {
	static int dist[][];
	static int N, M;
	static int[] v;
	public static int dfs(int cnt, int start, int cand_num){
		if(cnt == M + 1){
			int tdist = 0;
			int tmp = 0;
			int min;
			for(int i = 0 ; i < dist.length ; i++){ // i번째 집
				min = Integer.MAX_VALUE;
				for(int j = 0 ; j < dist[0].length ; j++){//j번째 치킨집
					if(v[j] == 1){ // 선택받은 집만
						tmp = dist[i][j];
						if(tmp < min && tmp != 0) min = tmp;
					}
				}
				tdist += min;
			}
			
			return tdist; 
		}

		int min = Integer.MAX_VALUE;
		int tmp = 0;
		for(int i = start ; i < cand_num ; i++){ // i번째 치킨집 유지
			if(v[i] == 1) continue;
			v[i] = 1;
			tmp = dfs(cnt+1, i + 1 , cand_num);
			v[i] = 0;
			if(tmp < min) { min = tmp; }
		}
		
		return min;
	}
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		int[][] map = new int[N][N];
		
		ArrayList<Integer> hx = new ArrayList<Integer>();
		ArrayList<Integer> hy = new ArrayList<Integer>();
		ArrayList<Integer> mx = new ArrayList<Integer>();
		ArrayList<Integer> my = new ArrayList<Integer>();
		
		for(int i = 0 ; i < N ; i++){
			for (int j = 0 ; j < N ; j++){
				map[i][j] = sc.nextInt();
				if(map[i][j] == 1){
					hx.add(j);
					hy.add(i);
				}
				else if(map[i][j] == 2){
					mx.add(j);
					my.add(i);
				}
			}
		}
		
		dist = new int[hx.size()][mx.size()];
		v = new int[mx.size()];
		
		for(int p = 0 ; p < hx.size() ; p++){
			for(int q = 0 ; q < mx.size() ; q++){
				dist[p][q] = Math.abs(hx.get(p) - mx.get(q)) +
							 Math.abs(hy.get(p) - my.get(q));
			}
			
		}
		System.out.println(dfs(1, 0, mx.size()));
	}
}