이번에는 치킨 배달이라는 문제를 풀어보았다. 오랜만에 백트래킹 문제를 풀면서 감을 살리기 위해 골드급 문제도 도전을 해보았다. 거의 근접하게 풀었는데 너무 어렵게 생각하였고 문제의 내용이 헷갈려서 조금 해맸던 문제이다.
🔥 문제
크기가 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개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
✍️ 문제 풀이
이 문제는 처음에 치킨집의 위치를 ArrayList에 담은 후 백트래킹을 이용하여 graph 배열에 표시한 후 dfs로 한 번 더 탐색하여 각각의 1에서의 거리를 측정하는 방식으로 구현하였지만 너무 복잡하기도 했고 시간 성능 면에서도 좋지 않아서 어떻게 할지 많이 해맸었다.
그래서 dfs를 한 번만 사용하는 로직으로 작성해 보았다.
처음 작성한 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
static int N;
static int M;
// 그래프
static int[][] graph;
static int[][] visited;
// 1의 좌표를 저장할 ArrayList
static ArrayList<int[]> houseLocation = new ArrayList<>();
// 2의 좌표를 저장할 ArrayList
static ArrayList<int[]> chickenLocation = new ArrayList<>();
static boolean[] chickenVisited;
static int result = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer info = new StringTokenizer(br.readLine());
N = Integer.parseInt(info.nextToken());
M = Integer.parseInt(info.nextToken());
// 그래프 생성
graph = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer nums = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(nums.nextToken());
if (num != 2) {
if (num == 1) houseLocation.add(new int[] {i, j});
graph[i][j] = num;
} else {
graph[i][j] = 0;
// 2인 값을 저장(치킨집 저장)
chickenLocation.add(new int[] {i, j});
}
}
}
// 최대 M만큼 치킨집 세우기
for (int i = 1; i < M + 1; i++) {
chickenVisited = new boolean[chickenLocation.size()];
dfs(0, i);
}
System.out.println(result);
}
private static void dfs(int current, int depth) {
if (current == depth) {
createVisited();
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (graph[i][j] == 2) {
for (int[] house : houseLocation) {
visited[house[0]][house[1]] = Math.min(visited[house[0]][house[1]], (Math.abs(i - house[0]) + Math.abs(j - house[1])));
}
}
}
}
for (int[] house: houseLocation) {
sum += visited[house[0]][house[1]];
}
result = Math.min(result, sum);
return;
}
for (int i = current; i < chickenLocation.size(); i++) {
if (!chickenVisited[i]) {
int[] location = chickenLocation.get(i);
graph[location[0]][location[1]] = 2;
chickenVisited[i] = true;
dfs(current + 1, depth);
graph[location[0]][location[1]] = 0;
chickenVisited[i] = false;
}
}
}
// 방문 리스트 생성
private static void createVisited() {
visited = new int[N][N];
for (int i = 0; i < N; i++) {
Arrays.fill(visited[i], 99999);
}
}
}위의 코드처럼 작성을 하니 문제에 주어진 테스트 케이스는 다 올바르게 나왔지만 시간 초과가 발생하였다... 좀 더 생각하다가 도저히 안 떠올라 결국 다른 분들의 코드를 참조하였다. ㅠㅠ
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
class Main {
static int N;
static int M;
static int[][] graph;
// 1의 좌표를 저장할 ArrayList
static ArrayList<int[]> houseLocation = new ArrayList<>();
// 2의 좌표를 저장할 ArrayList
static ArrayList<int[]> chickenLocation = new ArrayList<>();
static boolean[] chickenVisited;
static int result = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer info = new StringTokenizer(br.readLine());
N = Integer.parseInt(info.nextToken());
M = Integer.parseInt(info.nextToken());
graph = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer nums = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
int num = Integer.parseInt(nums.nextToken());
graph[i][j] = num;
if (num == 1) {
houseLocation.add(new int[] {i, j});
}
if (num == 2) {
chickenLocation.add(new int[] {i, j});
}
}
}
chickenVisited = new boolean[chickenLocation.size()];
dfs(0, 0);
System.out.println(result);
}
private static void dfs(int start, int depth) {
if (depth == M) {
int sum = 0;
// 각 부분별로
for (int[] house : houseLocation) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < chickenLocation.size(); i++) {
if (chickenVisited[i]) {
int chickenX = chickenLocation.get(i)[0];
int chickenY = chickenLocation.get(i)[1];
min = Math.min(min, Math.abs(house[0] - chickenX) + Math.abs(house[1] - chickenY));
}
}
sum += min;
}
result = Math.min(result, sum);
return;
}
for (int i = start; i < chickenLocation.size(); i++) {
if (!chickenVisited[i]) {
chickenVisited[i] = true;
dfs(i + 1, depth + 1);
chickenVisited[i] = false;
}
}
}
}문제에서 최대 M개를 고른다는 부분에서 잘못 이해하여 M개 이하로 선택하는 모든 경우를 의미한다고 생각하여 저장한 치킨집의 좌표들을 M개 이하의 조합으로 백트래킹을 진행했었다. 하지만 그게 아니었다. M개를 고른다는 의미였다... 또한 거리를 dfs로 구하려고 했던 것도 알고 보면 1의 좌표 즉, 집의 좌표도 치킨집의 좌표를 저장한 것처럼 저장한 후 백트래킹에서 return 하는 부분에서 맨해튼 거리로 계산하면 되는 문제였다.
이 2가지를 이해하고 나니 정말 간단한 코드로 구현할 수 있었다. 결론은 문제를 잘 이해하고 좀 복잡하거나 더러운 코드가 나온다면 시간 복잡도를 잘 생각해서 다른 아이디어로 생각해야 할 것이다.
