[swea - 10888] D4 - 음식배달

swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AXUqw9zKYaoDFASe&categoryId=AXUqw9zKYaoDFASe&categoryType=CODE

SW Expert Academy

 

이 문제와 비슷하다.

www.acmicpc.net/problem/15686

15686번: 치킨 배달

1. 유형

조합, bfs

 

2. 풀이

음식점은 선택하는 조합을 구한다. 구해진 조합대로 bfs를 돌린다.

 

3. 코드

package swea;

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

public class swea_10888음식배달 {
	static int ans,n;
	static int map[][];
	static int dr[] = {-1,1,0,0};
	static int dc[] = {0,0,-1,1};
	static class Pair{
		int r,c,d;
		public Pair(int r,int c,int d) {
			this.r=r;
			this.c=c;
			this.d=d;
		}
	}
	static ArrayList<Pair> list;
	static boolean sel[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t =sc.nextInt();
		for (int tc = 1; tc <= t; tc++) {
			n =sc.nextInt();
			map = new int[n][n];
			list = new ArrayList<>();
			
			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map.length; j++) {
					map[i][j] = sc.nextInt();
					if(map[i][j]>=2) {
						list.add(new Pair(i,j,0));
					}
				}
			}
			ans=Integer.MAX_VALUE;
			sel = new boolean[list.size()];
			comb(0);
			System.out.println("#"+tc+" "+ans);
		}//테케
	}
	
	static void comb(int arridx) {
		if(arridx == list.size()) {
			bfs(sel);
			return;
		}
		sel[arridx] = true;
		comb(arridx+1);
		sel[arridx] = false;
		comb(arridx+1);
	}
	
	static void bfs(boolean sel[]) {
		int sum=0;
		Queue<Pair> q = new LinkedList<>();
		boolean visit[][] = new boolean[n][n];
		for (int i = 0; i < sel.length; i++) {
			if(sel[i]) {
				q.add(new Pair(list.get(i).r,list.get(i).c,0));
				visit[list.get(i).r][list.get(i).c]=true;
				sum+=map[list.get(i).r][list.get(i).c];
			}
		}
		while(!q.isEmpty()) {
			Pair cur = q.poll();
			for (int i = 0; i < 4; i++) {
				int nr = cur.r + dr[i];
				int nc = cur.c + dc[i];
				int nd = cur.d + 1;
				if(nr<0 || nc<0 || nr>=n ||nc>=n) continue;
				if(visit[nr][nc]) continue;
				visit[nr][nc] = true;
				if(map[nr][nc]==1) {
					sum+=nd;
				}
				q.add(new Pair(nr,nc,nd));
			}
		}
		if(sum!=0) {
			ans = Math.min(sum, ans);
		}
	}
}