N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.
각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호)로 표현됩니다.
행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재하는
피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.
집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다.
예를 들어, 도시의 지도가 아래와 같다면
(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.
최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.
도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.
도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
둘째 줄부터 도시 정보가 입력된다.
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다.
둘째 줄부터 도시 정보가 입력된다.
4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2
6
public class 피자배달거리_DFS_삼성SW역량평가 {
static int n;
static int m;
static int[][] board;
static ArrayList<Point> house;
static ArrayList<Point> pizza;
//조합
static int[] combi;
static int minPizzaDistanceSum = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();//도시 지도 크기
m = in.nextInt();//살리고자 하는 피자집 개수
board = new int[n + 1][n + 1];//1-n까지
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
board[i][j] = in.nextInt();
}
}
house = new ArrayList<>();
pizza = new ArrayList<>();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (board[i][j] == 2)
pizza.add(new Point(i, j));
if (board[i][j] == 1)
house.add(new Point(i, j));
}
}
combi = new int[m];
dfs(0, 0);
//피자집 개수 중에 m개 뽑는 조합 구하기
System.out.println(minPizzaDistanceSum);
}
static void dfs(int L, int start) {
if (L == m) {
//조합 완성 combi
int sum = calDeliveryDistance(combi);
if (minPizzaDistanceSum >= sum) {
minPizzaDistanceSum = sum;
}
} else {
for (int i = start; i < pizza.size(); i++) {
combi[L] = i;
dfs(L + 1, i + 1);
}
}
}
static int calDeliveryDistance(int[] combi) {
//combi를 써야함
int minDistance = Integer.MAX_VALUE;
int sum = 0;
for (Point h : house) {
//각 피자집들에 대해서 배달거리 구하고 최솟값 찾기
for (int index : combi) {
Point p = pizza.get(index);
int dis = Math.abs(p.x - h.x) + Math.abs(p.y - h.y);
if (minDistance >= dis) {
minDistance = dis;
}
}
sum += minDistance;
minDistance = Integer.MAX_VALUE; //초기화
}
return sum;
}
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
}
문제 보자마자 이차원배열에 거리를 구한다? 이건 전문제들같이 방향 돌면서 하면 되겠네..라고 무식하게 생각하고 알고리즘을 고안했음.
처음에 생각한 알고리즘은 다음과 같음.
for(전체 탐색)
if(board==1)
for(방향 8개 검색)
if(board==2)
배달거리 계산
대충 크게 이런식으로 하면 되지 않을까 생각했는데 이 경우에 m개를 선택해서 조합에 대한 배달거리 계산을 해야하는데 어디에서 할지 코드를 짜다보니 방향이 안잡혀서 고민하다가 강의를 들었음.
코드자체는 참고안하고 arraylist사용하고 조합쓰는 아이디어만 알아내고 다시 짰음.
house arraylist와 pizza arraylist 선언
for(전체)
if(house)
house.add
if(pizza)
pizza.add
pizza집중 m개 조합 구하기 -> 조합 구현 후 combi배열에 넣기
조합 구해질 때마다 m개의 각 피자집에 대한 집들의 배달 거리 구하고 그 중 최솟값을 sum에 저장 (sum:도시의 최소 배달거리, 즉 모든 집의 최소배달거리의 합)
조합마다 sum을 내므로 sum중에서 가장 최소 sum 비교 후 출력
문제 풀고나서 느낀점
: 삼성 역량 평가는 나의 범위가 아니겠구나..
열심히 공부해야지.. 오늘도 눈물 한방울