백준 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개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.
둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.
도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.
출력
첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.
내 답
1차 시도 (오답)
1. 도시 상황을 2차원 배열에 입력, 치킨집 좌표를 chickens 리스트에 저장
2. 모든 치킨집 중 M개의 치킨집을 선택하는 조합 메서드를 재귀함수를 이용해 구현. pick 배열에 저장
3. map을 탐색하며 집일 경우 BFS를 통해 최단거리를 구하고, 최소값을 선택.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class G5_치킨배달 {
static class Chicken {
int r, c;
public Chicken() {
}
public Chicken(int r, int c) {
super();
this.r = r;
this.c = c;
}
@Override
public String toString() {
return "Chicken [r=" + r + ", c=" + c + "]";
}
}
static int N, M, min;
static int[][] map;
static int[][] tmpMap;
static boolean[][] visited;
static ArrayList<Chicken> chickens;
static Chicken[] pick;
static int[] dr = {-1, 1, 0, 0};
static int[] dc = {0, 0, -1, 1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
min = Integer.MAX_VALUE; // 치킨 거리의 최소값을 저장할 변수
map = new int[N][N];
tmpMap = new int[N][N];
visited = new boolean[N][N];
chickens = new ArrayList<>(); // 치킨집 좌표를 담을 리스트
pick = new Chicken[M]; // M개를 뽑은 후 저장할 배열
// 맵 입력 및 치킨집 탐색
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
map[r][c] = sc.nextInt();
if (map[r][c] == 2) {
chickens.add(new Chicken(r, c));
map[r][c] = 0; // 지도상으로는 0으로 초기화
}
}
}
pick(0, 0);
System.out.println(min);
}
private static void pick(int n, int r) {
// 모두 골랐으면 탐색 시작
if (r >= M) {
editMap();
int tmpDist = search();
if (min > tmpDist) {
min = tmpDist;
}
return;
}
// 남은 치킨집 수보다 골라야 할 치킨집 수가 많으면 부적절하므로 종료
if (n >= chickens.size()) {
return;
}
// 해당 치킨집을 안고른다
pick(n + 1, r);
// 해당 치킨집을 고른다
pick[r] = chickens.get(n);
pick(n + 1, r + 1);
}
// 선택한 치킨집만 지도상에 2로 표시
private static void editMap() {
for (int r=0; r<N; r++) {
tmpMap[r] = map[r].clone();
}
for (Chicken chicken : pick) {
tmpMap[chicken.r][chicken.c] = 2;
}
}
// 지도 탐색하여 집일 경우 BFS탐색하여 거리 계산
private static int search() {
int sum = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (tmpMap[r][c] == 1) {
int dist = BFS(r, c);
sum += dist;
}
}
}
return sum;
}
private static int BFS(int r, int c) {
Queue<int[]> q = new LinkedList<>();
int dist = 0;
int size = 1;
visited = new boolean[N][N];
visited[r][c] = true; // 시작지점 방문체크
q.add(new int[] { r, c }); // 큐에 삽입
while (!q.isEmpty()) {
for (int i = 0; i < size; i++) {
int[] curr = q.poll();
// 치킨집이면 탐색 종료
if (tmpMap[curr[0]][curr[1]] == 2) {
return dist;
}
// 4방탐색
for (int dir = 0; dir<4; dir++) {
int nr = curr[0] + dr[dir];
int nc = curr[1] + dc[dir];
if (nr<0 || nr>=N || nc<0 || nc>=N || visited[nr][nc]) continue;
q.add(new int[] {nr, nc});
visited[nr][nc] = true;
}
}
size = q.size();
dist += 1;
}
return dist;
}
}
2차 시도 (정답)
이전 시도에서 최단거리를 구하기 위한 방법으로 BFS를 선택했으나,
BFS는 사방을 탐색해가며 최단거리를 구할 때 배열 크기가 커지고 집과 치킨집 간 거리가 멀어질수록
급격히 비효율적으로 변함을 느꼈다.
따라서 미리 집과 치킨집의 좌표를 저장해두고, 일일히 계산하는 방법으로 코드를 수정했다 !
1. 도시 상황을 2차원 배열에 입력, 치킨집과 집의 좌표를 각각 chickens, houses 리스트에 저장
2. 모든 치킨집 중 M개의 치킨집을 선택하는 조합 메서드를 재귀함수를 이용해 구현. pick 배열에 저장
3. 집과 치킨집 간 거리를 모두 계산한 후 최소값을 선택한다.
public class G5_치킨배달 {
static class Chicken {
int r, c;
public Chicken() {
}
public Chicken(int r, int c) {
super();
this.r = r;
this.c = c;
}
@Override
public String toString() {
return "Chicken [r=" + r + ", c=" + c + "]";
}
}
static class House {
int r, c;
public House() {
// TODO Auto-generated constructor stub
}
public House(int r, int c) {
super();
this.r = r;
this.c = c;
}
@Override
public String toString() {
return "House [r=" + r + ", c=" + c + "]";
}
}
static int N, M, min;
static int[][] map;
static ArrayList<Chicken> chickens;
static ArrayList<House> houses;
static Chicken[] pick;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
min = Integer.MAX_VALUE; // 치킨 거리의 최소값을 저장할 변수
map = new int[N][N];
chickens = new ArrayList<>(); // 치킨집 좌표를 담을 리스트
houses = new ArrayList<>(); // 집 좌표를 담을 리스트
pick = new Chicken[M]; // M개를 뽑은 후 저장할 배열
// 맵 입력 및 치킨집 탐색
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
map[r][c] = sc.nextInt();
if (map[r][c] == 2) {
chickens.add(new Chicken(r, c));
map[r][c] = 0; // 지도상으로는 0으로 초기화
} else if (map[r][c] == 1) {
houses.add(new House(r, c));
}
}
}
pick(0, 0);
System.out.println(min);
}
private static void pick(int n, int r) {
// 모두 골랐으면 탐색 시작
if (r >= M) {
int tmpDist = search();
if (min > tmpDist) {
min = tmpDist;
}
return;
}
// 남은 치킨집 수보다 골라야 할 치킨집 수가 많으면 부적절하므로 종료
if (n >= chickens.size()) {
return;
}
// 해당 치킨집을 안고른다
pick(n + 1, r);
// 해당 치킨집을 고른다
pick[r] = chickens.get(n);
pick(n + 1, r + 1);
}
// 모든 집 탐색하며 선택한 각 치킨집과의 최소 거리를 구해 마을의 총 치킨거리 계산
private static int search() {
int sum = 0;
for (House h : houses) {
int tmpMin = Integer.MAX_VALUE;
for (Chicken c : pick) {
tmpMin = Math.min(Math.abs(h.r-c.r)+Math.abs(h.c-c.c), tmpMin);
}
sum += tmpMin;
}
return sum;
}
}
복습 사항
배열 깊은 복사(deep copy)
깊은복사는 배열의 주소값이 아닌 실제 값을 복사하는 것을 말함
일반적으로 copyArr = originArr 의 방식으로 복사하면 원본 배열의 주소값이 복사되기 떄문에,
copyArr의 값을 수정하면 originArr의 값도 같이 변한다!
따라서 깊은 복사가 필요할 땐 아래와 같이 할 것
int[][] newMap = new int[N][N];
for (int i = 0; i < N; i++) {
newMap[i] = map[i].clone(); // 각 행을 개별적으로 복사
}
