lango

찍먹? 부먹?
난 부먹 개발자.

2 minute read



문제 풀이

이번 문제는 DFS를 통한 백트래킹을 이용해 풀 수 있다.


아이디어 도출

문제 풀이를 위해 생각한 아이디어는 다음과 같다.

  1. 집과 치킨집의 위치를 미리 저장한다.
  2. M개만큼 뽑은 치킨집은 방문 여부를 체크하여 도시의 치킨 거리를 구할 때 사용한다.
  3. M개의 치킨집을 모두 뽑았다면, 모든 집의 위치에서 최소거리에 있는 치킨집과의 거리을 구한다.
  4. 그렇게 모든 치킨집과의 최소거리를 계산한다면, 모든 도시의 치킨거리 중 최솟값을 구하면 된다.


문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

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

class Main {    

    // 방문배열과 입력배열
    static boolean[] visited;
    static int[][] map;
    
    // 집과 치킨집 좌표를 저장할 List
    static ArrayList<int[]> house;
    static ArrayList<int[]> chicken;
    
    // 입력배열의 크기인 N과 깊이 M
    static int N, M;

    // 도시의 치킨거리 최솟값을 저장할 변수
    static int result;

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

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

        map = new int[N][N]; 
        house = new ArrayList<>();
        chicken = new ArrayList<>();


        /**
         * 위치들을 입력받으며 house, chicken List 초기화
         */
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                
                // 집의 위치와 치킨집의 위치를 저장
                if(map[i][j] == 1) {
                    house.add(new int[]{i, j});
                } else if(map[i][j] == 2) {
                    chicken.add(new int[]{i, j});
                }
            }
        }

        // 치킨집 크기만큼 방문 배열을 초기화
        visited = new boolean[chicken.size()];  
        
        // 최솟값을 구해야 하므로 result를 Integer.MAX_VALUE 값으로 초기화
        result = Integer.MAX_VALUE;

        // DFS 재귀함수 호출
        recursion(0, 0);

        bw.write(result+"\n");
        
        bw.close();
        br.close();
    }

    /**
     * 백트래킹을 진행할 DFS 재귀함수
     * depth(깊이)가 M과 같아지면 선택한 치킨집과 집과의 치킨 거리를 구한다.
     * 치킨거리 중 최솟값을 누적시키며, 모든 도시의 치킨 거리 중 최솟값을 구한다.
     */
    public static void recursion(int depth, int at) {
        
        if(depth == M) {            
            
            // 도시의 치킨거리
            int sum = 0;
            
            for(int i=0; i<house.size(); i++) {
                int min = Integer.MAX_VALUE;

                // 집과 치킨 집 중 방문한 치킨집의 모든 거리를 비교하며 최소거리를 구한다.
                for(int j=0; j<chicken.size(); j++) {
                    if(visited[j]) {
                        // 해당 집의 치킨 거리 |r1-c1|+|r2-c2|
                        int distance = Math.abs(house.get(i)[0] - chicken.get(j)[0])
                                    + Math.abs(house.get(i)[1] - chicken.get(j)[1]);
                        min = Math.min(min, distance);
                    }
                }
                sum += min;
            }

            result = Math.min(result, sum);
            return;

        }

        // 백트래킹 탐색 진행
        for(int i=at; i<chicken.size(); i++) {
            // 방문 여부를 통해 가지치기
            if(!visited[i]) {
                visited[i] = true;
                recursion(depth+1, i+1);
                visited[i] = false;
            }

        }
        
    }    

}

출처

  • 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.

You may also enjoy