[Java] 15686번: 치킨 배달

🌎 Link : https://www.acmicpc.net/problem/15686

15686번: 치킨 배달

---

💡 접근 방법

1. 문제 이해 & 적합한 알고리즘 찾기

최대 치킨집의 개수(M) 개에서 가장 작은 치킨거리를 구하는 문제다. 모든 최대 치킨집의 개수를 확인하면서 최소의 값을 찾으면 되기 때문에 백트레킹을 사용을 하는 게 좋아 보인다. 비슷한 알고리즘으로 브루트 포스가 있는데 차이점을 확인해 보자.

• 브루트 포스 : 모든 경우의 수를 확인함 / 노가다 / 최적해를 보장한다
• 백트레킹 : 모든 경우의 수를 확인하지만 를 해서 원하는 조건에 만족하지 못하면 탐색중단 후 이전 단계로 돌아감 / 가지치기

2. 문제 풀이

백트레킹 알고리즘은 BFS, DFS와 마찬가지로 어느 정도 정해진 규격이 있다. 원하는 조건을 설정하고 탈출하는 것이다. 여기서 방문체크를 하는 이유는 모든 경우의 수를 확인을 하기 위해서다. 무슨 말이냐면 만약 4개의 치킨집 중에서 2개를 선택해야 하는 경우에, (1,2), (1,3), (1,4), (2,3), (2,4), (3,4)와 같이 총 6가지의 조합을 전부 구해서 최소 치킨거리를 구해야 하기 때문이다. 

private static void backtracking(int start, int depth) {
	// 탈출조건 현재 문제로 최대의 치킨집(M)개를 계산하면 메서드 종료
        if (depth == M) {
            calculate();
            return;
        }

        for (int i = start; i < chicken.size(); i++) {
            isVisited[i] = true;
            backtracking(i + 1, depth + 1);
            isVisited[i] = false;
        }
}

 

또한 밑의 calculate() 메서드를 보면 여기서도 방문체크를 통해서 최대 치킨집(M) 개를 기준으로 최소 치킨값을 계산한다. 이게 말이 좀 이상한테 출력코드를 추가해서 확인해 보면 더 쉽게 이해가 갈 것이다.

private static void backtracking(int start, int depth) {
	if (depth == M) {
		calculate();
		// 출력 부분
		System.out.print("isVisited =");
		for(int i = 0; i < isVisited.length ; i++) {
			if(isVisited[i]) System.out.print(i + " ");
		}

		System.out.println();
		return;
	}

	for (int i = start; i < chicken.size(); i++) {
		isVisited[i] = true;
		backtracking(i + 1, depth + 1);
		isVisited[i] = false;
	}
}

// 입력 값
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2

// 결과
isVisited = 0 1 
isVisited = 0 2 
isVisited = 0 3 
isVisited = 0 4 
isVisited = 1 2 
isVisited = 1 3 
isVisited = 1 4 
isVisited = 2 3 
isVisited = 2 4 
isVisited = 3 4

 

이렇게 모든 조합을 찾아보는 것을 확인할 수 있다. 마지막으로 작동방식을 요약하자면 이렇게 설명할 수 있을 거 같다.

1. backTracking() 메서드 실행
   • for문을 통해 모든 치킨집을 방문한다 / 여기서 포인트는 최대 치킨집(M)을 맞추기 위해 depth를 + 1 씩 해준다.
2. 그렇게 최대 치킨집(M) 개를 만족하는 depth가 나왔다 그럼 calculate() 메서드 실행
   • 현재 최대 치킨집의 개수(M) 개의 치킨집이 방문체크가 되어있으므로 방문체크가 된 치킨집과 집의 치킨거리를 구한다.
   • 그런 다음 answer = Math.min(answer, sum)을 통해 치킨거리를 갱신한다.
3. 그럼 탐색 종료 후 이전 노드로 돌아가 1번 for문으로 다시 돌아가서 실행

4개의 치킨집 중에 최대 치킨집의 수가 2라면 처음 0,1로 계산하고 저기서 for 문으로 돌아가 0,2로 계산하고 또 0,3으로 계산하는 식으로 진행된다.

---

🗝 풀이 코드

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

public class Main {
    static int N, M, answer;
    static int[][] map;
    static boolean[] isVisited;
    static List<Point> house, chicken;

    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());
        answer = Integer.MAX_VALUE;

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

        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 Point(i, j));
                if (map[i][j] == 2) chicken.add(new Point(i, j));
            }
        }

        isVisited = new boolean[chicken.size()];
        backtracking(0, 0);
        System.out.println(answer);
    }

    private static void backtracking(int start, int depth) {
        if (depth == M) {
            calculate();
            return;
        }

        for (int i = start; i < chicken.size(); i++) {
            isVisited[i] = true;
            backtracking(i + 1, depth + 1);
            isVisited[i] = false;
        }
    }

    private static void calculate() {
        int sum = 0;
        for (int i = 0; i < house.size(); i++) {
            int temp = Integer.MAX_VALUE;
            for (int j = 0; j < chicken.size(); j++) {
                if (isVisited[j]) {
                    int dist = Math.abs(house.get(i).x - chicken.get(j).x)
                            + Math.abs(house.get(i).y - chicken.get(j).y);
                    temp = Math.min(temp, dist);
                }
            }

            sum += temp;
        }

        answer = Math.min(answer, sum);
    }
}

class Point {
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}