[BOJ - JAVA] 15686 - 치킨 배달 (완전 탐색, 백트래킹)

# 주소

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

15686번: 치킨 배달

# 문제

# 문제 해설 및 코드 리뷰

import java.awt.Point;
import java.util.ArrayList;
import java.util.Scanner;
public class Main{
	static int min = Integer.MAX_VALUE;
	static int[][] arr;
	static int n, m;
	static boolean[] visit;
    static ArrayList<Point> HouseList = new ArrayList<>();
    static ArrayList<Point> ChickenList = new ArrayList<>();
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();
        arr = new int[n][n];
        for(int i = 0; i < n; i++) {
        	for(int j = 0; j < n; j++) {
        		arr[i][j] = scan.nextInt();
        		if(arr[i][j] == 1)
        			HouseList.add(new Point(i,j));
        		else if(arr[i][j] == 2)
        			ChickenList.add(new Point(i,j));
        	}
        }
        visit = new boolean[ChickenList.size()];
        backtracking(0, 0);
        System.out.println(min);
    }
    public static void backtracking(int x, int y) {
    	if(x == m) {
    		int sum = 0;
    		for(int i = 0; i < HouseList.size(); i++) {
    			int count = Integer.MAX_VALUE;
    			for(int j = 0; j < ChickenList.size(); j++) {
    				if(visit[j] == true) {
    					int dist = Math.abs(HouseList.get(i).x - ChickenList.get(j).x)
    							+ Math.abs(HouseList.get(i).y - ChickenList.get(j).y);
    					count = Math.min(count, dist);
    				}
    			}
    			sum += count;
    		}
    		min = Math.min(min, sum);
    		return;
    	}
    	for(int i = y; i < ChickenList.size(); i++) {
    		if(visit[i] == false) {
    			visit[i] = true;
    			backtracking(x+1, i+1);
    			visit[i] = false;
    		}
    	}
    }
}

제가 풀어본 백트래킹 문제 중 가장 난이도가 있었습니다.

비교적 간단한 백트래킹만 풀어본 것 같아서 어려운걸 풀기 위해 정답률이 40%대인걸로 골랐습니다.

이 문제가 알고보니까 삼성 SM 테스트? 에서 나온건가봐요.

삼성이 백트래킹 문제를 정말 좋아한다고 하던데, 아무래도 많이 풀어놓는게 좋겠네요.

백트래킹을 제가 정말 오랜만에 풀어서 기억이 드문드문 납니다만 원리는 간단합니다.

 

자 총 8개의 공이 있다고 했을 때 2개의 공을 선택하려면 우린 8C2라는 조합 공식을 이용해서 구할 수 있죠?

컴퓨터에선 이것을 구하기 위해서 백트래킹이라는 기법을 사용합니다.

무슨 말이냐면, 8개 중 2개의 공을 고르고 또 다른 2개의 공을 집고, 또 다른 2개의 공을 집고 이런 식으로 계속해서 모든 경우의 수를 만족하기 위해 일일히 2개씩 다 구합니다.

이것이 백트래킹이고 브루트 포스(완전 탐색) 문제에서도 빈번히 사용됩니다.

이 문제에선 일단 ArrayList를 2개를 선언해야 합니다.

(전 1개만 선언하고 계속 문제를 뚫어져라 봤는데 도저히 감이 안잡혀서... 서칭을 좀 했습니다.. ㅠㅠ 백트래킹인건 이해하고 있었는데 2개로 선언하는걸 이번에 또 배워가네요.)

어쨌든 ArrayList를 각각 하나는 HouseList로서 1이 들어가는 Point들을 담을 거구요. 나머지 한 개는 ChickenList로서 arr가 2가 되는 모든 점들을 저곳에 담을 것입니다.

그리고 나서 visit을 꼭, 반드시, 무조건 선언해주셔야 하는데 이것을 선언하지 않으면 중복된 값을 다시 선언하는.. 중복조합의 형태가 될 수 있기 때문에 반드시 선언해주셔야 중복을 피할 수 있겠습니다.

그래서 visit = new boolean이라 선언하고 이것의 크기는 당연히 2의 개수. 즉, ChickenList의 크기가 되겠습니다.

이제 백트래킹을 한 번 실행한 결과가 정답이 되면 되는데 이 백트래킹의 구문이 백트래킹을 이해하는데 굉장히 중요합니다.

일단 x와 y를 인자로 받아들입니다. 

여기서 x는 인덱스이므로 m이 될 때마다 (폐업되지 않고 살아남는 치킨집) 나머지 치킨집은 무시하고 시민들이 사는 집까지의 "치킨 거리"를 각각 구합니다.

첫 번째 for문 안의 HouseList와 두 번째 for문의 ChickenList범위 까지의 for문에서의 내용은 나중에 설명드리겠습니다. 밑으로 내려가셔서 제일 밑의 for문 먼저 보겠습니다.

for(int i = y; i < ChickenList.size(); i++) {
    		if(visit[i] == false) {
    			visit[i] = true;
    			backtracking(x+1, i+1);
    			visit[i] = false;
    		}
    	}

여기가 진짜 진짜 중요합니다.

백트래킹의 가장 핵심이 되는 구문이 바로 여기이지요.

이 for문이 실행되는 조건은 x가 m이 아닐 때입니다.

그 말은 즉슨, 치킨집을 최대로 장사할 수 있게 만드는 치킨집의 수가 아직 m개 안채워졌으므로 방문하지 않은 visit[인덱스]에 대해 visit을 true로 바꾸고 백트래킹을 다시 실행하겠다는 의미이며 다시 실행할 때마다 x+1(x == m이 되면 if문으로 들어감)과 i+1을 해준 뒤 visit = false 이렇게 바꾸어 주시면 모든 경우의 수를 구할 수 있습니다.

아까의 예로 들어봅시다.

8개의 공(번호가 적혀있는) 중 3개의 공을 택한다 했을 때, 저 구문만 입력하면

1 , 2 , 3 or 1 , 2 , 4 or , 1 , 2 , 5 , ... , 6 , 7 , 8 까지 총 8C3 = 56가지가 나온다는 의미입니다.

근데 여기서 visit조건을 다 없애고 그냥 제일 밑의 for문 대신 backtracking(x+1, i+1)만 실행하게 되면

1, 1 , 1 , or 1 , 1 , 2 or 1 , 1 , 3 , ... , 8, 8 , 8 까지 엄청난 경우의 수가 튀어나와 버리죠.

정답과는 거리가 멀겠죠? 우리가 사용해야할 방법은 당연히 위에 서술한 "조합"을 사용해야 합니다.

그럼 이제 다시 위로 올라가서 if(x == m)일 때를 살펴보겠습니다.

이 때에는 컴퓨터가 공의 개수가 3개 즉, 치킨 집의 개수 3개를 다 골랐다는 의미가 됩니다.

그리고 이중 for문에서 본격적으로 계산을 합니다.

이 때 꼭 필요한 구문이 if(visit[j] == true)이 부분입니다.

우리는 제일 밑의 for문에서 선택된 치킨집은 visit이 true로 바뀐다는 사실을 인지해야 합니다.

그렇기 때문에 위의 if(visit == true) 이 말은, 선택된 치킨집의 HouseList.get(i).x - ChickenList.get(j).x 이렇게 입력하게 되면 집과 치킨집까지의 거리를 각각 구하게 되고 이를 count에 담아 sum에 더해줍니다.

이 때 더해지는 모든 sum들을 min에 담을텐데, 이 min은 치킨집의 수가 3개 선택할 때마다 계속해서 min에 새로운 치킨 거리가 저장이 됩니다.

다만 기존의 min보다 작을 때만 min에 저장이 됩니다.

그리고 꼭 빼먹지 말아야 할 부분이 return;까지 입력해주셔야 백트래킹이 완성이 되요.

이 return을 입력 안하면 함수가 저기서 끝나버리게 되거든요.

그러므로 return을 입력해주시고 다시 backtracking구문으로 들어갈 수 있게 해주셔야 겠습니다.

감사합니다. 

꼭 질문해주세요. 어려운게 있으면 !