문제

치킨 배달

풀이

문제에서 요구하는 답은 도시에 있는 치킨집 M개를 고르는데 가장 거리가 짧은 치킨 거리를 구하는 것이다. 가장 거리가 짧은 거리를 구하는데 DFS 로 풀기위해서는 갈 수 있을만큼 최대로 많이 가고 갈수 없으면 이전 정점으로 돌아가는 방법을 사용한다. 모든 치킨집을 한번씩 방문 하여야 한다. 그래서 방문 여부를 확인 할 수 있는 배열을 선언하여 flag 값으로 두어 이전 값과 구분을 한다.

1. 집과 치킨집의 위치를 따로 리스트로 담는다

		chicken = new ArrayList<>();
        person = new ArrayList<>();
        map = new int[n][n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 1) { // 집
                    person.add(new Map(i, j));
                } else if (map[i][j] == 2) { // 치킨집
                    chicken.add(new Map(i, j));
                }
            }
        }

2. m개의 매장을 만들기 위해 백트래킹을 하여 가장 짧은 거리를 연산한다

	/**
     * 백트레킹
     * 
     * @param start 시작점
     * @param count 치킨 매장
     */
    public static void dfs(int start, int count) {
        if (count == m) {
            // m 개의 매장이 되었을때에 가장 짧은 거리
        }
		
        // 치킨집의 개수만큼 백트래킹을 한다
        for (int i = start; i < chicken.size(); i++) {
            visited[i] = true;
            dfs(i + 1, count + 1);
            visited[i] = false;
        }
    }

• 연산 내용은 문제에서 준 |x1-x2|+|y1-y2| 연산으로 거리를 계산 해준다

			int length = 0;
            for (int i = 0; i < person.size(); i++) {
                int temp = Integer.MAX_VALUE; // 범위 넘는 경우 방지
                for (int j = 0; j < chicken.size(); j++) {
                    if (visited[j]) {
                        int distance = Math.abs(person.get(i).x - chicken.get(j).x)
                                + Math.abs(person.get(i).y - chicken.get(j).y);
                        temp = Math.min(temp, distance);
                    }
                }
                length += temp;
            }
            answer = Math.min(answer, length);
            return;

연습을 더 많이 해봐야 더 와닿을 것 같다. 여기저기 많이 응용되는 부분이 많다. 차이점을 명확하게 알고 풀면 더 좋을 것 같다

전체 코드

전체 코드