[Algorithm] SW 기출문제 - 치킨 배달(15686) 자바 풀이

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 백준 SW 기출문제 치킨 배달 자바 풀이를 작성하고자 합니다.

 

문제 출처: https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

 

 

1. 풀이 소스

 

import java.util.*;
import java.io.*;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = parseInt(st.nextToken());
        int m = parseInt(st.nextToken());
        ChickenDistance chickenDistance = new ChickenDistance(n, m);
        
        for (int row = 1; row <= n; row++) { // 1행 1열 이므로
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= n; col++)
                chickenDistance.setMap(row, col, parseInt(st.nextToken()));
        }
        
        chickenDistance.start();
        
        System.out.println(chickenDistance.getMinDistance());
    }
}

class ChickenDistance {
    int n; // 정사각형 행렬
    int m; // m개의 선택된 치킨집
    boolean[] open; // 열려있는 집
    int minDistance = Integer.MAX_VALUE; // 최소 치킨 거리
    List<Point> chickens = new ArrayList<>(); // 치킨집 좌표
    List<Point> homes = new ArrayList<>(); // 집 좌표
    
    ChickenDistance(int n, int m) {
        this.n = n;
        this.m = m;
    }
    
    void setMap(int row, int col, int value) {
        if (value == 1) homes.add(new Point(row, col)); // 1이라면 집에 추가
        else if (value == 2) chickens.add(new Point(row, col)); // 2라면 치킨집 추가
    }
    
    void start() {
        open = new boolean[chickens.size()]; // 열려 있는집 초기화하기
        
        dfs(0, 0); // dfs
    }
    
    void dfs(int start, int cnt) {
        if (cnt == m) {            
            int minLocalDistance = 0; // 현재 dfs에서 지역변수 Distance 초기화  (모든 집이 거리 비교 끝나면 비교)

            for (Point home : homes) { // 집 리스트 순회
                int distance = Integer.MAX_VALUE; // 비교할 거리는 최대치로 초기화
                for (int i = 0; i < chickens.size(); i++) {
                    if (open[i]) { // 만약 열려 있다면
                        Point ch = chickens.get(i);
                        int nowD = Math.abs(home.row - ch.row) + Math.abs(home.col - ch.col);
                        distance = Math.min(nowD, distance); // 치킨집과 비교해서 거리 업데이트
                    }
                }
                minLocalDistance += distance;
            }
            
            minDistance = Math.min(minLocalDistance, minDistance);
            return;
        }
        
        for (int i = start; i < chickens.size(); i++) {
            open[i] = true; // 집 열려 있도록 설정
            dfs(i + 1, cnt + 1); // 다음 재귀로 조합 설정
            open[i] = false; // 백트래킹으로 다시 초기화함으로써, 다음 재귀에 영향 받지 않도록 설정
        }
    }
    
    int getMinDistance() {
        return minDistance;
    }
    
    static class Point {
        int row;
        int col;
        
        Point (int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}

 

 

2. 풀이 중점 사항

 

해당 문제는 백트래킹으로 해결하는 방법이 있습니다.

재귀를 수행할 때, m개의 치킨집을 선정한 후, 각 집에서 치킨집을 순회하며 거리를 측정해야 했습니다.

따라서, 먼저 백트래킹으로  치킨집을 여는 방법으로 m개의 조합이 설정될 수 있도록 하였습니다.

 

for (int i = start; i < chickens.size(); i++) {
    open[i] = true; // 집 열려 있도록 설정
    dfs(i + 1, cnt + 1); // 다음 재귀로 조합 설정
    open[i] = false; // 백트래킹으로 다시 초기화함으로써, 다음 재귀에 영향 받지 않도록 설정
}

 

만약 총 m개의 치킨집이 선택이 된다면 (open이 먼저 true가 되므로 총 m가 true)

int minLocalDistance = 0; // 현재 dfs에서 지역변수 Distance 초기화  (모든 집이 거리 비교 끝나면 비교)

for (Point home : homes) { // 집 리스트 순회
    int distance = Integer.MAX_VALUE; // 비교할 거리는 최대치로 초기화
    for (int i = 0; i < chickens.size(); i++) {
        if (open[i]) { // 만약 열려 있다면
            Point ch = chickens.get(i);
            int nowD = Math.abs(home.row - ch.row) + Math.abs(home.col - ch.col);
            distance = Math.min(nowD, distance); // 치킨집과 비교해서 거리 업데이트
        }
    }
    minLocalDistance += distance;
}

minDistance = Math.min(minLocalDistance, minDistance);
return;
}

 

minLocalDistance를 0으로 초기화한 후 집을 순회하며 가장 적은 거리의 치킨집을 업데이트합니다. 그리고, 하나의 집에 대한 치킨 거리가 업데이트되면, minLocalDistance에 최소 거리를 더하여 다음 집의 치킨 거리를 업데이트합니다.

 

이렇게 모든 집 업데이트가 끝나면, minDistance를 업데이트하고 return 합니다.

이어서 다음 재귀가 실행되고 cnt == m이되면 이와 같은 방법을 진행하되, 백트래킹으로 인해 다른 조합을 가진 오픈 치킨집이 설정되게 됩니다.

 

이상으로 치킨 거리 문제 풀이를 마치도록 하겠습니다.

감사합니다!!