[백준] 15686번 치킨배달 (시뮬, bfs, 파이썬, java)

www.acmicpc.net/problem/15686

15686번: 치킨 배달

1. python 풀이 

from collections import deque
import math
from itertools import combinations


chicken,house=[],[]

n,m=map(int,input().split())

for y in range(n):
    temp=list(map(int,input().split()))
    for x in range(len(temp)):
        if temp[x]==1:
            house.append((y,x))
        elif temp[x]==2:
            chicken.append((y,x))

allcase=combinations(chicken,m)

def distance(case,house):
    res=0
    for y,x in house:
        tmp=math.inf # 각 집에서 치킨집까지 최소거리
        for yy,xx in case:
            if tmp>abs(yy-y)+abs(xx-x):
                tmp=abs(yy-y)+abs(xx-x)
        res+=tmp

    return res

answer=math.inf
for case in allcase:
    tmp=distance(list(case),house)
    if answer>tmp:answer=tmp

print(answer)

2. 자바 풀이

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int map[][];
	static ArrayList<Integer[]> chicken=new ArrayList<>();
	static ArrayList<Integer[]> house=new ArrayList<>();
	static int n,m;
	static int ans=Integer.MAX_VALUE;
	static boolean vis[];
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				int cur=sc.nextInt();
				if(cur==1) {
					house.add(new Integer[] {i,j});
				}else if(cur==2) {
					chicken.add(new Integer[] {i,j});
				}
			}
		}
		vis=new boolean[chicken.size()];
		nCr(0,0);
		System.out.println(ans);
	} 
	
	
		
	private static void check() {
		ArrayList<Integer> distance=new ArrayList<>();
		for (int i = 0; i < house.size(); i++) {
			int cur=Integer.MAX_VALUE;
			int y=house.get(i)[0];
			int x=house.get(i)[1];
			for (int j = 0; j < chicken.size(); j++) {
				if(vis[j]==false)continue;
				int diff=Math.abs(y-chicken.get(j)[0])+Math.abs(x-chicken.get(j)[1]);
				if(diff<cur)cur=diff;
			}
			distance.add(cur);
		}
		Collections.sort(distance);
		int temp=0;
		for (int i = 0; i < distance.size(); i++) {
			temp+=distance.get(i);
		}
		if(temp<ans)ans=temp;
	}
	
	private static void nCr(int cnt,int start) {
		if(cnt==m) {
			check();
			return;
		}
		for (int i = start; i < chicken.size(); i++) {
			if(vis[i]==true)continue;
			vis[i]=true;
			nCr(cnt+1,i+1);
			vis[i]=false;
		}
		
	}

}