백준 15686번 : 치킨 배달 java

이 문제는 정해진 개수의 치킨집에서 가장 짧은 거리를 이동하여 지도에 있는 모든 집들에 배달을 마무리할 수 있게 하는 문제입니다.

이 문제는 소스 코드를 보면서 설명해드리도록 하겠습니다.

---

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

public class Main{
    static int N, M;
    static int[][] map;
    static LinkedList<rowCol> chicken = new LinkedList<>();
    static int min = Integer.MAX_VALUE;
    static int[] drow = {0, 0, 1, -1};
    static int[] dcol = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];

        for(int i = 0; i<N; i++){
            st = new StringTokenizer(br.readLine());

            // 값을 입력받으면서 LinkedList에 미리 치킨집의 좌표 입력
            for(int j = 0; j<N; j++) {
                int space = Integer.parseInt(st.nextToken());
                map[i][j] = space;

                if(space == 2) {
                    chicken.add(new rowCol(i, j, 0));
                    map[i][j] = 0;
                }
            }
        }

        dfs(0, 0);
        System.out.println(min);
    }

    static void dfs(int count, int idx){
        //선택한 치킨집의 갯수가 M과 같아지면 bfs
        if(count == M){
            bfs();
            return;
        }
        //이전에 선택했더 치킨집은 확인하지 않아도 되므로 i는 idx에서 시작
        for(int i = idx; i<chicken.size(); i++){
            rowCol rc = chicken.get(i);
            int row = rc.row;
            int col = rc.col;

            if(map[row][col] == 2)
                continue;

            map[row][col] = 2;
            dfs(count+1, i);
            map[row][col] = 0;
        }
    }

    static void bfs(){
        int[][] sub = new int[N][N];
        Queue<rowCol> q = new LinkedList<>();
        int sum = 0;

        //원본 데이터를 보존하기 위하여 새로운 배열을 만들면서 이전 dfs에서
        //폐업하지 않기로 선택한 치킨집이 어딘지 확인
        for(int i = 0; i<N; i++){
            for(int j = 0; j<N; j++){
                sub[i][j] = map[i][j];

                if(sub[i][j] == 2)
                    q.offer(new rowCol(i, j, 0));
            }
        }

        while(!q.isEmpty()){
            rowCol a = q.poll();

            for(int i = 0; i<4; i++){
                int dr = a.row + drow[i];
                int dc = a.col + dcol[i];

                if(dr<0||dc<0||dr>=N||dc>=N)
                    continue;
                //한번 이동한 공간은 다시 가지 않으므로 3을 넣어놓음
                if(sub[dr][dc] == 0){
                    sub[dr][dc] = 3;
                    q.offer(new rowCol(dr, dc, a.cnt+1));
                }
                //bst를 이용하였을 때 가장 먼저 집에 도착한 치킨집이
                //가장 가까운 치킨집이므로 sub[dr][dc]를 4로 초기화하고 큐에 삽입
                else if(sub[dr][dc] == 1){
                    sub[dr][dc] = 4;
                    q.offer(new rowCol(dr, dc, a.cnt+1));

                    sum += a.cnt+1;
                }
            }
        }

        min = Math.min(min, sum);
    }
}
//row col좌표 뿐만이 아니라 치킨집에서 얼마나 거리가 떨어져 있는지 알기 위해서 cnt사용
class rowCol{
    int row, col, cnt;

    rowCol(int row, int col, int cnt){
        this.row = row;
        this.col = col;
        this.cnt = cnt;
    }
}

코드 안의 주석에 대부분의 내용들은 설명하였습니다.

이제 그림을 통해서 이 문제를 조금 더 상세히 설명하겠습니다.

 

왼쪽의 그림은 위 문제의 예제 1번을 나타낸 그림입니다.

치킨집은 초록색 블럭, 배달해야 되는 집은 파란색 블록으로 표시하였습니다.

이 문제에서 남겨야하는 치킨집은 3개이므로 치킨집은 지금 있는 3개가 그대로 남습니다.

 

 

따라서 바로 bst를 실행하고 bst 안의 while문이 거리
1까지의 블록들을 처리했을 때의 모습입니다.

이미 지나간 블럭들은 주황색으로 표시하였습니다.

괄호 안의 숫자들은 그 칸까지 배달할 때의
최소거리입니다.

 

 

이제 모든 집들에 배달이 완료되었습니다.

그렇다면 각각의 집들까지의 배달할 때의 거리의
최솟값인 5를 얻을 수 있습니다.

거리가 3일 때까지를 구하면 (5, 5)좌표에 위치한
치킨집에서도 (2, 5)또는 (4, 3)에 위치한 집에 배달할 수 있지만 이전에 이미 더 가까운 거리에서 배달한 집이 있으므로 계산하지 않아도 됩니다.