[백준] 15686 - 치킨 배달

[문제링크]

15686번: 치킨 배달

 

0. 치킨집의 총 개수를 모르므로 arraylist로 관리

  - 살릴 치킨집의 개수는 알고 있으므로 배열로 관리

 

1. 가능한 모든 살릴수 있는 치킨집의 조합을 구한다 (combi 함수)

 

2. 각 조합에 대해, 치킨집 위치를 시작으로 bfs를 돌려 모든 집까지의 최소 거리를 구한다 (bfs함수)

 

3. bfs함수에서 구한 최소 거리가 더 작다면 min을 갱신

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

	static boolean[][]isV;//방문체크
	static int[][]map;
	static int[][]select;//살릴 치킨집
	static List<int[]>chicken;//모든 치킨집
	static int ans,n,m;
	static Queue<int[]> qu;
    
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
		
		map = new int[n+2][n+2];
		chicken = new ArrayList<>();
		//-1 패딩
		for (int i = 0; i < n+2; i++) {
			map[i][0]=-1;map[i][n+1]=-1;
			map[0][i]=-1;map[n+1][i]=-1;
		}
		
		//입력받기 + 치킨집 저장
		for (int i = 1; i <= n; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				map[i][j]=pint(st.nextToken());
				if(map[i][j]==2)chicken.add(new int[] {i,j});
			}
		}
		
		ans=Integer.MAX_VALUE;
		select=new int[m][2];
		combi(0, 0);
		System.out.println(ans);
        
	}
    
	static void combi(int cnt, int prev) {
		if(cnt==m) {
			qu = new LinkedList<int[]>();
			for (int i = 0; i < m; i++) {
				qu.offer(new int[] {select[i][0], select[i][1], 0});
			}
			ans = Math.min(ans, bfs());
			return;
		}
		
		for (int i = prev, len = chicken.size(); i < len; i++) {
			select[cnt][0]=chicken.get(i)[0];
			select[cnt][1]=chicken.get(i)[1];
			combi(cnt+1, i+1);
		}
	}
	
	static int bfs() {
		isV = new boolean[n+2][n+2];
		int dist=0;
		while(!qu.isEmpty()) {
			int[] cur = qu.poll();
			
			if(map[cur[0]][cur[1]]==1) {
				dist+=cur[2];
			}
			
			if(!isV[cur[0]+1][cur[1]] && map[cur[0]+1][cur[1]]>=0) {
				isV[cur[0]+1][cur[1]]=true;
				qu.offer(new int[] {cur[0]+1, cur[1], cur[2]+1});
			}
			if(!isV[cur[0]-1][cur[1]] && map[cur[0]-1][cur[1]]>=0) {
				isV[cur[0]-1][cur[1]]=true;
				qu.offer(new int[] {cur[0]-1, cur[1], cur[2]+1});
			}
			if(!isV[cur[0]][cur[1]+1] && map[cur[0]][cur[1]+1]>=0) {
				isV[cur[0]][cur[1]+1]=true;
				qu.offer(new int[] {cur[0], cur[1]+1, cur[2]+1});
			}
			if(!isV[cur[0]][cur[1]-1] && map[cur[0]][cur[1]-1]>=0) {
				isV[cur[0]][cur[1]-1]=true;
				qu.offer(new int[] {cur[0], cur[1]-1, cur[2]+1});
			}
			
		}
		
		return dist;
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면