티스토리 뷰
[JAVA] 백준 #15686 치킨 배달 🍗 | BackTracking | 디버깅 활용하는 방법 | 재귀 함수
YouJungJang 2024. 5. 9. 01:03[JAVA] 백준 #15686 치킨 배달
https://www.acmicpc.net/problem/15686
🔒 문제
크기가 N×N인 도시가 있다. 도시는 1 ×1 크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.
이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.
예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2
0은 빈칸, 1은 집, 2는 치킨집이다.
(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.
(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.
이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프랜차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개라는 사실을 알아내었다.
도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
🔎 풀이
연구소 문제와 비슷해 보여서 dfs로 조합을 찾고 bfs로 거리를 구하면 되겠다! 하고 시도했는데 수도 없는 메모리 초과 + 시간 초과를 받았다. 이런 비슷한 유형의 문제를 몇 개 풀어봤는데 이 문제는 풀이 방법이 기존 것과 달라서 역시 정해진 방법이나 정답은 없고, 문제풀이를 많이 해봐야 하는구나 하고 다양한 문제 풀이의 중요성을 깨달았다.
특이하게도 입력받은 도시 정보를 이중 배열에 저장할 필요도 없고, 조합을 구할 때 visited를 사용할 필요도 없다. 또한 bfs를 사용하면 시간 초과가 발생하므로 Arraylist와 for문 루프를 사용해서 시간을 훨씬 단축할 수 있다. 자세한 풀이는 다음과 같다.
[0] 필요한 자료 구조
- ArrayList<int[]> chickenJip : 모든 치킨집 좌표를 담는다.
- ArrayList<int[]> houses: 모든 가정집 좌표를 담는다.
- ArrayList<int[]> choice: M만큼 선택한 치킨집 좌표를 담는다 ➡️ 백트래킹 사용해서 조합할 수 있는 모든 경우의 수 구할 것이다.
[1] pickChickenJip
이 문제의 관건은 '살려둘 치킨집 M개의 조합을 어떻게 생성할 것인가'이다. 초반에 풀이할 때는 이중 배열에 도시 데이터를 미리 담아두고 visited를 사용해 조합을 구성해 나갔는데 ArrayList를 사용해 가정집과 치킨집 좌표만 담아두면 이중 배열이 필요할 일이 전혀 없다.
우선 모든 치킨집 좌표를 담은 ArrayList의 인덱스들을 for문을 사용해서 백트래킹으로 조합한다.
이때 for문의 시작점은 start + 1부터 시작하도록 설정되어 있어서 for문의 i는 무조건 전달받은 start보다 큰 상태에서 반복되므로 visited 배열로 방문 체크를 구현할 필요가 없다.
재귀적으로 매서드를 호출하다가 choice의 크기, 즉 count가 M과 같다면 치킨거리를 구하는 매서드 getChickenDistance()를 호출하고 리턴한다.
현재 i 인덱스에 있는 치킨집을 초이스에 담고, 현재 치킨집을 담은 상태에서 백트래킹을 실시하면
"현재 치킨집을 담아서 M개의 치킨집 조합을 생성해 치킨 거리를 구하는 모든 경우의 수를 구한 뒤" 리턴된다.
그럼 현재 치킨집을 사용해 조합한 경우는 모두 구했으니 초이스에서 제거하고, 다음 인덱스에 있는 치킨집으로 for문이 넘어간다.
public static void pickChickenJip(int count, int start ){
if( count == M ){
getChickenDistance();
return;
}
for( int i = start; i < chickenJip.size(); i++ ){
int[] now = chickenJip.get(i);
//[1] 해당 치킨집 선택하기
choice.add(now);
//[2] 백트래킹
pickChickenJip(count + 1, i + 1 );
//[3] 백트래킹 완료하면 선택 취소
choice.remove(now);
}
}// end of pickChickenJip
백트래킹 조합이 이해가 가지 않아서 인텔리제이의 디버거 기능을 사용해 직접 choice 배열이 갱신되어 가는 모습을 확인했다.
우선 예제 입력은 다음과 같다.
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다음과 같은 예제를 입력받을 경우 모든 치킨집 위치를 담는 chickenJip 배열은 아래와 같이 채워진다.
[[0,1], [3,0], [4,0], [4,1], [4,4]]
우선 pickChickenJip메서드에서 choice 조합이 완성되는 3번 줄에 중단점을 두고 실행하면 다음과 같이 콘솔창에 현재 우리가 생성한 각 변수들에 담긴 값을 확인할 수 있다.
처음 백트래킹을 실행했을 때 choice 배열에는 [0,1], [3,0]이 첫 번째 조합으로 입력된다.
치킨집 배열에서의 인덱스로 생각하면 (0,1)이다.
다음 실행하면 [0,1], [4,0] 즉 (0,2)가 나온 것을 확인할 수 있고,
세 번째 실행하면 [0,1], [4,1] 즉 (0,3)이 담겨있다.
이렇게 백트래킹을 사용해서 구현할 때 실행 과정이 이해가지 않으면 디버거를 사용해서 직접 눈으로 확인할 수 있다.
[2] pickChickenJip
public static void getChickenDistance(){
int totalDistance = 0;
for( int[] home : houses){
int chickenDistance = Integer.MAX_VALUE;
for( int[] chicken : choice ){
int distance = Math.abs(home[0]-chicken[0]) + Math.abs(home[1]-chicken[1]);
if( distance < chickenDistance ) chickenDistance = distance;
}
totalDistance += chickenDistance;
}
if( MIN > totalDistance ) MIN = totalDistance;
}// end of getChickenDistance자, 그럼 살려둘 치킨집 조합을 구했으니 그 조합으로 만드는 '치킨 거리'를 구해보자.
나는 여기서 헤맸던 부분이 분명 각 가정집과 가장 가까운 치킨집과의 거리가 치킨거리니까
그럼 각 가정집에서 가장 가까운 치킨집을 찾기 위해 bfs를 사용해서 구현했고, 여기서 시간 초과가 발생했다.
하지만 그렇게 최소 거리의 치킨집을 찾는 것보다 그냥 루프를 사용해서 가정집과 choice에 담긴 치킨집들의 치킨거리를 각각 구하고, 거기서 최소 거리를 구하는 방법이 훨씬 빠르다.
🔹 전체 코드
import java.util.*;
public class Main {
static int N;
static int M;
static ArrayList<int[]> chickenJip = new ArrayList<>();
static ArrayList<int[]> houses = new ArrayList<>();
static ArrayList<int[]> choice = new ArrayList<>();
static int MIN = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer line = new StringTokenizer(bf.readLine(), " ");
N = Integer.parseInt(line.nextToken());
M = Integer.parseInt(line.nextToken());
for( int i = 0; i < N; i++ ){
line = new StringTokenizer(bf.readLine(), " ");
for( int j = 0; j < N; j++ ){
int n = Integer.parseInt(line.nextToken());
if( n == 2 ) chickenJip.add(new int[]{i,j});
if( n == 1 ) houses.add(new int[]{i,j});
}
}
pickChickenJip( 0, 0 );
System.out.println(MIN);
}// end of main
public static void pickChickenJip(int count, int start ){
if( count == M ){
getChickenDistance();
return;
}
for( int i = start; i < chickenJip.size(); i++ ){
int[] now = chickenJip.get(i);
//[1] 해당 치킨집 선택하기
choice.add(now);
//[2] 백트래킹
pickChickenJip(count + 1, i + 1 );
//[3] 백트래킹 완료하면 선택 취소
choice.remove(now);
}
}// end of pickChickenJip
public static void getChickenDistance(){
int totalDistance = 0;
for( int[] home : houses){
int chickenDistance = Integer.MAX_VALUE;
for( int[] chicken : choice ){
int distance = Math.abs(home[0]-chicken[0]) + Math.abs(home[1]-chicken[1]);
if( distance < chickenDistance ) chickenDistance = distance;
}
totalDistance += chickenDistance;
}
if( MIN > totalDistance ) MIN = totalDistance;
}// end of getChickenDistance
}// end of class