삼성 SW 역량 평가
인프런, 자바(Java) 알고리즘 문제풀이
DFS, BFS 활용 - 0814. 피자 배달 거리(DFS)
🗒️ 문제
🎈 나의 풀이
private static int size, maxPizza;
private static int[][] map;
private static List<Point> pizzas = new ArrayList<>();
private static List<Point> houses = new ArrayList<>();
private static List<List<Point>> pizzaList = new ArrayList<>();
private static class Point {
int x, y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
private static void DFS(int L, List<Point> pizzaCombi) {
if (pizzaCombi.size() > maxPizza) return;
if (L == pizzas.size()) {
if (pizzaCombi.size() == maxPizza) pizzaList.add(new ArrayList<>(pizzaCombi));
return;
}
DFS(L + 1, new ArrayList<>(pizzaCombi));
pizzaCombi.add(pizzas.get(L));
DFS(L + 1, new ArrayList<>(pizzaCombi));
}
private static int solution() {
int answer = Integer.MAX_VALUE;
// 1. 전체 피자집에서 maxPizza 개수 만큼의 피자집을 선택하는 경우의 수(DFS)
DFS(0, new ArrayList<>());
// 2. 각 집과 선택된 피자집과의 거리 합 구하기
for (List<Point> list : pizzaList) {
int sum = 0;
for (Point house : houses) {
int distance = Integer.MAX_VALUE;
for (Point pizza : list) {
distance = Math.min(distance, Math.abs(house.x - pizza.x) + Math.abs(house.y - pizza.y));
}
sum += distance;
}
answer = Math.min(answer, sum);
}
return answer;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
size = sc.nextInt();
maxPizza = sc.nextInt();
map = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
map[i][j] = sc.nextInt();
if (map[i][j] == 1) houses.add(new Point(i, j));
else if (map[i][j] == 2) pizzas.add(new Point(i, j));
}
}
System.out.println(solution());
}🖍️ 강의 풀이
class Point{
public int x, y;
Point(int x, int y){
this.x=x;
this.y=y;
}
}
class Main {
static int n, m, len, answer=Integer.MAX_VALUE;
static int[] combi;
static ArrayList<Point> hs, pz;
public void DFS(int L, int s){
if(L==m){
int sum=0;
for(Point h : hs){
int dis=Integer.MAX_VALUE;
for(int i : combi){
dis=Math.min(dis, Math.abs(h.x-pz.get(i).x)+Math.abs(h.y-pz.get(i).y));
}
sum+=dis;
}
answer=Math.min(answer, sum);
}
else{
for(int i=s; i<len; i++){
combi[L]=i;
DFS(L+1, i+1);
}
}
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
n=kb.nextInt();
m=kb.nextInt();
pz=new ArrayList<>();
hs=new ArrayList<>();
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
int tmp=kb.nextInt();
if(tmp==1) hs.add(new Point(i, j));
else if(tmp==2) pz.add(new Point(i, j));
}
}
len=pz.size();
combi=new int[m];
T.DFS(0, 0);
System.out.println(answer);
}
}💬 짚어가기
해당 문제는 DFS를 이용하여 풀 수 있다. 나의 풀이에서는 2 단계로 나누어 접근하였다.
- 전체 피자 가게 중에
M개의 피자 가게를 선택하는 모든 경우의 수를 찾는다.
:DFS를 이용하여 가능한 조합을 모두 찾는다. - 선택된 피자 가게와 각 집과의 최소 거리의 합을 구한다.
: 최소 거리 합이 가장 작은 경우를 찾아 문제를 해결한다.
구현한 코드는 다음과 같다. 좌표 보관을 위해 클래스 Point를 생성하였고, 이를 담을 수
있는 List를 2개 생성하여 피자 집 정보와 집의 정보를 나눠 보관하도록 하였다.
1. 피자 집 조합 구하기
이제 피자 집 정보를 담은 리스트 중에서 M개의 피자 집을 선택하는 모든 경우의 수를 찾는다.
DFS를 수행하며 선택된 피자 집은 pizzaCombi : List<Point>에 담고, 조합된 경우의 수
pizzaCombi는 pizzaList : List<List<Point>>에 담는다.
2. 최소 거리 구하기
다음으로 각 집과 선택된 피자 집 사이의 최소 거리의 합을 구한다. pizzaList를 순회하며
pizzaCombi를 하나 선택하고, 집 리스트에서 최소 거리의 합을 구하여 문제를 해결한다.
강의에서도 동일한 로직으로 문제를 해결한다. 차이점으로는 피자 집 조합을 보관할 때, 따로
객체를 담을 수 있는 리스트를 두지 않고, 해당 객체의 인덱스를 보관할 수 있는 int 배열을
이용하였다.
또, 경우의 수를 찾을 때 마다 바로 집과의 거리를 계산하여 최소 거리를 갱신하도록 하였다.
𝑶𝒏𝒆 𝒅𝒂𝒚 𝒐𝒓 𝒅𝒂𝒚 𝒐𝒏𝒆.