블로그를 쓰는 것이 어려운 것 같다. 누군가가 읽기 좋게, 정보 전달을 목적으로 글을 쓰는 것은 어렵다. 말로는 잘 할 수 있는데..~
오늘 푼 문제는 백준 15686 - 치킨배달 문제이다 ! 골드5 문제이다.
문제
크기가 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 20은 빈 칸, 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개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
예제
입력1
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2출력1
5입력2
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출력2
10입력3
5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0출력3
11입력4
5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1출력4
32풀이 방법
이 문제는 M개의 치킨가게로 가장 적은 치킨 거리를 만드는 문제이다 !
처음에는 전체에서 M개만을 남기고 치킨집을 제거하려고 했다. 그래서 BFS로 가장 가까운 치킨집을 찾으려하였고, 제거할 치킨집을 고르는 기준을 고민하였다. 그런데 그 과정에서 고려할 것이 너무 많았다. 예를 들면 같은 거리에 있는 치킨집이 2개 이상이면 어쩌지, 가장 적은 고객에게 영향을 주는 치킨 집을 제거하였으나 그 것을 제거했을 때, 그 고객이 할당되는 치킨집이 너무 먼 곳이라 더 많은 고객을 가진 치킨집을 없애는 것 보다 비효율적이면 어떡하지 등등 결론이 나지 않았다. 그래서 이 방법이 아니구나 생각했다. ( 이 과정에 정말 오랜 시간을 들였다.. 거의 한시간 방법을 바꾸고는 후루룩 풀었다. )
이 과정에서 문제 분류를 확인하였는데, 그리디였다.. 그래서 내가 풀던 방법이 맞는데 내가 기준을 못 정한건가.. 방향을 틀어도 되나 잠시 방황했지만 한 시간이나 고민해도 나오지 않는 답을 붙들고 있을 수는 없어서 새로운 방법을 생각했다. ( 문제의 분류가 왜 그리디인가 고민한 결과 아마도 문제에서 최대 M개라고 되어있지만 사실 M개를 다 남기는 경우가, 그 보다 작게 남기는 경우와 같을지언정 크지는 않기에 그런 관점에서 그리디라고 한 것이 아닐까 생각했다. )
이 때 생각난 다른 풀이는 주어진 치킨집 중에서 M개를 뽑는 모든 조합을 구한 후, 각 경우의 치킨 거리를 계산하여 가장 작은 값을 출력하는 것이다. 사실 이 방법도 금방 떠올렸던 방법이지만 뭔가 이게 너무 비효율적이진 않은가 고민을 많이했다. 하지만 입력 범위를 보면 굉장히 작기 때문에 이 방법을 사용해도 된다고 생각했다.
그래서 치킨집의 좌표를 리스트로 만들고, 인덱스를 이용하여 DFS + 백트래킹으로 조합을 구했다. 그리고 고객 좌표 리스트도 만들어서 모든 고객에 대해서 해당 조합 경우에 치킨 거리를 구하고 이를 이용하여 도시의 치킨 거리를 구했다. 모든 조합에 대해서 이 과정을 반복하며 가장 작은 값을 구해 반환하였다.
물론 입력 값이 작아서 문제 없을거라고 생각했지만, 그래도 이 방법이 제일 효율적일까 계속 고민이 들었다. 그래서 지금 상황에서 더 최적화 할 수 있는 부분이 있을까 고민했다. 각 조합 상황에서 치킨 거리를 구할 때, 최적화 할 수 있을만한 부분이 두 개 생각났다.
- 먼저 모든 집에 대해서 치킨 거리를 구해서 제일 작은 값을 구하는 지금의 방법이 아니라, 지금 조합의 치킨집들에 대해서 BFS로 가장 가까운 고객을 찾는게 더 빠를까? 하는 아이디어였다. 하지만 잠깐만 생각해봐도 절대 빠르다는 보장이 없다는 것을 알 수 있었다. 오히려 기존대로 하는것이 평균적으로 더 빠를 것 같았다.
- 다음으로 A치킨집과 B고객 사이의 거리를 매 조합마다 다시 계산하지 않고 2차원 배열에 저장해두고 가져다가 쓰는 것이다. 이것 역시 거리를 계산하는 것이 여러 계산 과정을 거치는 복잡한 알고리즘이 아닌 단순 계산이기에 시간, 메모리 전체적인 효율성을 고려했을 때 그렇게 메리트가 없다고 판단하였다.
결국은 아무것도 수정하지않고 제출을 했고, 통과했다 !
이번 문제를 풀면서 내가 고민을 너무 많이하고, 너무 비효율적일까봐 걱정을 많이 하느라 시간을 잡아먹느다는 생각을 했다 ! 물론 연습과정에서는 도움이 되겠지만 실전을 위해서는 고쳐야 할 것 같다 !
코드
import java.io.*;
import java.util.*;
public class Main {
static class Point{
private int x;
private int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
static class Solution{
private int m;
private boolean[] visited;
private ArrayList<Point> chickens;
private ArrayList<Point> customers;
private int result;
Solution(int m, ArrayList<Point> chickens, ArrayList<Point> customers){
this.m = m;
this.chickens = chickens;
this.customers = customers;
this.visited = new boolean[chickens.size()];
this.result = Integer.MAX_VALUE;
}
void combination(int current, int count){
if(count == m){
Point chicken, customer;
int chicken_dis;
int city_dis = 0;
for(int i=0; i<customers.size(); i++){
customer = customers.get(i);
chicken_dis = Integer.MAX_VALUE;
for(int j=0; j<chickens.size(); j++){
if(visited[j]){
chicken = chickens.get(j);
chicken_dis = Math.min(chicken_dis,
(Math.abs(customer.x-chicken.x)+Math.abs(customer.y-chicken.y)));
}
}
city_dis += chicken_dis;
}
result = Math.min(result, city_dis);
return;
}
for(int i=current; i<chickens.size(); i++){
visited[i] = true;
combination(i+1, count+1);
visited[i] = false;
}
}
int solution(){
combination(0, 0);
return result;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
StringTokenizer st; // tokenizer
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
ArrayList<Point> chickens = new ArrayList<>();
ArrayList<Point> customers = new ArrayList<>();
int temp;
for(int r=0; r<n; r++){
st = new StringTokenizer(br.readLine());
for(int c=0; c<n; c++){
temp = Integer.parseInt(st.nextToken());
if(temp == 1) customers.add(new Point(r, c));
else if(temp == 2) chickens.add(new Point(r, c));
}
}
Solution solution = new Solution(m, chickens, customers);
bw.write(String.valueOf(solution.solution()));
bw.write( "\n"); // for return value
bw.flush(); // flush
bw.close(); // close
br.close(); // close
}
}