피자 배달 거리(삼성 SW 역량평가 기출/DFS)

이 문제는 DFS(깊이 우선 탐색)을 활용하여 조합을 구하는 문제이다. N x N 크기의 도시에서 M개의 피자집을 선택하여 도시의 피자 배달 거리를 최소화하는 것이 목표다. 각 집은 도시의 여러 피자집 중 하나와 연결되며, 그 집에서 가장 가까운 피자집까지의 거리를 계산해, 모든 집의 배달 거리 합이 최소가 되도록 해야 한다.

 

문제 설명

도시 지도는 N x N 크기로 주어지며, 각 칸은 빈칸(0), 집(1), 피자집(2)으로 표현된다. 각 집마다 여러 피자집과의 거리가 존재하지만, 그중 최소 거리가 해당 집의 피자 배달 거리가 된다. 예를 들어, (1, 2)에 있는 집과 (2, 3)에 있는 피자집의 거리는 |1-2| + |2-3| = 2이다.

이 문제는 도시에서 M개의 피자집을 선택하여, 전체 도시의 피자 배달 거리를 최소화하는 M개의 피자집을 선택하는 것이 목표다.

 

입력 설명

• 첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
• 둘째 줄부터 N x N 크기의 도시 정보가 입력된다.
  • 0은 빈칸, 1은 집, 2는 피자집을 의미한다.

출력 설명

• M개의 피자집이 선택되었을 때 도시의 최소 피자 배달 거리를 출력한다.

입력 예시

4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2

 

출력 예시

6

 

문제 해결 과정

1. 격자판 입력
   도시의 크기 N과 선택할 피자집의 개수 M을 입력받은 후, 도시 정보를 2차원 배열로 저장한다. 집(1)의 좌표는 house 리스트에, 피자집(2)의 좌표는 pizza 리스트에 저장한다.
2. 조합 탐색 (DFS)
   M개의 피자집을 선택하기 위한 조합을 구하는 데 DFS를 사용한다. combi[] 배열을 통해 선택된 피자집의 인덱스를 저장하고, 선택된 피자집에 대한 조합을 생성한 후 각 조합에 대해 도시의 피자 배달 거리를 계산한다.
3. 치킨 거리 계산
   선택된 피자집 조합에 대해, 각 집에서 가장 가까운 피자집과의 거리를 계산한다. 모든 집의 배달 거리 합을 구한 후, 이를 최소값으로 갱신한다.

코드 구현

package com.example.codingtest;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

// 좌표를 저장하는 Point 클래스 정의
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;  // 도시 크기 N, 선택할 피자집 수 M, 피자집의 총 개수 len, 최소 피자 배달 거리 answer
    static int[] combi;  // 피자집 조합을 저장할 배열
    static ArrayList<Point> house, pizza;  // 집 좌표와 피자집 좌표를 저장할 리스트

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  // 입력을 받기 위한 BufferedReader
        StringTokenizer st = new StringTokenizer(br.readLine());  // 첫 줄을 공백으로 구분하여 입력받음
        N = Integer.parseInt(st.nextToken());  // 도시의 크기 N 입력
        M = Integer.parseInt(st.nextToken());  // 선택할 피자집의 개수 M 입력

        pizza = new ArrayList<>();  // 피자집 좌표를 저장할 리스트
        house = new ArrayList<>();  // 집 좌표를 저장할 리스트

        // 도시 정보를 입력 받음
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());  // 각 행을 공백으로 구분하여 입력받음
            for (int j = 0; j < N; j++) {
                int tmp = Integer.parseInt(st.nextToken());  // 현재 좌표의 값을 저장
                if (tmp == 1) {  // 값이 1이면 집이므로 집 리스트에 좌표를 저장
                    house.add(new Point(i, j));
                } else if (tmp == 2) {  // 값이 2이면 피자집이므로 피자집 리스트에 좌표를 저장
                    pizza.add(new Point(i, j));
                }
            }
        }

        len = pizza.size();  // 피자집의 총 개수를 저장
        combi = new int[M];  // 선택된 피자집 조합을 저장할 배열

        DFS(0, 0);  // DFS 탐색 시작 (L=0, s=0)

        System.out.println(answer);  // 계산된 최소 피자 배달 거리 출력
    }

    // DFS 함수: 피자집 M개를 선택하는 모든 조합을 구하는 함수
    public static void DFS(int L, int s) {
        if (L == M) {  // 피자집 M개를 선택한 경우
            int sum = 0;  // 각 집에 대한 피자 배달 거리의 합을 저장할 변수
            for (Point h : house) {  // 모든 집에 대해 반복
                int dis = Integer.MAX_VALUE;  // 현재 집과 선택된 피자집 중 가장 가까운 거리를 저장
                for (int i : combi) {  // 선택된 피자집의 인덱스를 통해 거리 계산
                    // 집과 피자집 사이의 거리를 계산하고, 가장 짧은 거리로 업데이트
                    dis = Math.min(dis, Math.abs(h.x - pizza.get(i).x) + Math.abs(h.y - pizza.get(i).y));
                }
                sum += dis;  // 해당 집의 최소 피자 배달 거리를 합산
            }
            answer = Math.min(answer, sum);  // 전체 최소 피자 배달 거리로 업데이트
        } else {  // 아직 M개의 피자집을 선택하지 않은 경우
            for (int i = s; i < len; i++) {  // 선택할 피자집의 조합을 탐색
                combi[L] = i;  // L번째 피자집 선택
                DFS(L + 1, i + 1);  // 다음 피자집 선택을 위해 재귀 호출 (L+1, i+1)
            }
        }
    }
}

• DFS 활용: 피자집을 선택하는 조합을 DFS로 구한다. 이를 통해 M개의 피자집을 선택하고, 각 조합에 대해 도시의 피자 배달 거리를 계산한다.
• 맨해튼 거리: 각 집과 피자집 사이의 거리는 |x1 - x2| + |y1 - y2|로 계산된다.
• 최소 거리 갱신: 각 조합마다 구한 피자 배달 거리 합을 비교하여 최소값을 찾는다.

 

결론

이 문제는 DFS를 활용하여 피자집 M개의 조합을 구하고, 각 조합에 대해 도시의 피자 배달 거리를 계산하는 문제이다. 피자집을 선택하는 다양한 경우를 고려한 후 최적의 피자 배달 거리를 구하는 것이 목표다.