안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.
이번 포스팅은 백준 SW 기출문제 치킨 배달 자바 풀이를 작성하고자 합니다.
문제 출처: https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
1. 풀이 소스
import java.util.*;
import java.io.*;
import static java.lang.Integer.parseInt;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = parseInt(st.nextToken());
int m = parseInt(st.nextToken());
ChickenDistance chickenDistance = new ChickenDistance(n, m);
for (int row = 1; row <= n; row++) { // 1행 1열 이므로
st = new StringTokenizer(br.readLine());
for (int col = 1; col <= n; col++)
chickenDistance.setMap(row, col, parseInt(st.nextToken()));
}
chickenDistance.start();
System.out.println(chickenDistance.getMinDistance());
}
}
class ChickenDistance {
int n; // 정사각형 행렬
int m; // m개의 선택된 치킨집
boolean[] open; // 열려있는 집
int minDistance = Integer.MAX_VALUE; // 최소 치킨 거리
List<Point> chickens = new ArrayList<>(); // 치킨집 좌표
List<Point> homes = new ArrayList<>(); // 집 좌표
ChickenDistance(int n, int m) {
this.n = n;
this.m = m;
}
void setMap(int row, int col, int value) {
if (value == 1) homes.add(new Point(row, col)); // 1이라면 집에 추가
else if (value == 2) chickens.add(new Point(row, col)); // 2라면 치킨집 추가
}
void start() {
open = new boolean[chickens.size()]; // 열려 있는집 초기화하기
dfs(0, 0); // dfs
}
void dfs(int start, int cnt) {
if (cnt == m) {
int minLocalDistance = 0; // 현재 dfs에서 지역변수 Distance 초기화 (모든 집이 거리 비교 끝나면 비교)
for (Point home : homes) { // 집 리스트 순회
int distance = Integer.MAX_VALUE; // 비교할 거리는 최대치로 초기화
for (int i = 0; i < chickens.size(); i++) {
if (open[i]) { // 만약 열려 있다면
Point ch = chickens.get(i);
int nowD = Math.abs(home.row - ch.row) + Math.abs(home.col - ch.col);
distance = Math.min(nowD, distance); // 치킨집과 비교해서 거리 업데이트
}
}
minLocalDistance += distance;
}
minDistance = Math.min(minLocalDistance, minDistance);
return;
}
for (int i = start; i < chickens.size(); i++) {
open[i] = true; // 집 열려 있도록 설정
dfs(i + 1, cnt + 1); // 다음 재귀로 조합 설정
open[i] = false; // 백트래킹으로 다시 초기화함으로써, 다음 재귀에 영향 받지 않도록 설정
}
}
int getMinDistance() {
return minDistance;
}
static class Point {
int row;
int col;
Point (int row, int col) {
this.row = row;
this.col = col;
}
}
}
2. 풀이 중점 사항
해당 문제는 백트래킹으로 해결하는 방법이 있습니다.
재귀를 수행할 때, m개의 치킨집을 선정한 후, 각 집에서 치킨집을 순회하며 거리를 측정해야 했습니다.
따라서, 먼저 백트래킹으로 치킨집을 여는 방법으로 m개의 조합이 설정될 수 있도록 하였습니다.
for (int i = start; i < chickens.size(); i++) {
open[i] = true; // 집 열려 있도록 설정
dfs(i + 1, cnt + 1); // 다음 재귀로 조합 설정
open[i] = false; // 백트래킹으로 다시 초기화함으로써, 다음 재귀에 영향 받지 않도록 설정
}
만약 총 m개의 치킨집이 선택이 된다면 (open이 먼저 true가 되므로 총 m가 true)
int minLocalDistance = 0; // 현재 dfs에서 지역변수 Distance 초기화 (모든 집이 거리 비교 끝나면 비교)
for (Point home : homes) { // 집 리스트 순회
int distance = Integer.MAX_VALUE; // 비교할 거리는 최대치로 초기화
for (int i = 0; i < chickens.size(); i++) {
if (open[i]) { // 만약 열려 있다면
Point ch = chickens.get(i);
int nowD = Math.abs(home.row - ch.row) + Math.abs(home.col - ch.col);
distance = Math.min(nowD, distance); // 치킨집과 비교해서 거리 업데이트
}
}
minLocalDistance += distance;
}
minDistance = Math.min(minLocalDistance, minDistance);
return;
}
minLocalDistance를 0으로 초기화한 후 집을 순회하며 가장 적은 거리의 치킨집을 업데이트합니다. 그리고, 하나의 집에 대한 치킨 거리가 업데이트되면, minLocalDistance에 최소 거리를 더하여 다음 집의 치킨 거리를 업데이트합니다.
이렇게 모든 집 업데이트가 끝나면, minDistance를 업데이트하고 return 합니다.
이어서 다음 재귀가 실행되고 cnt == m이되면 이와 같은 방법을 진행하되, 백트래킹으로 인해 다른 조합을 가진 오픈 치킨집이 설정되게 됩니다.
이상으로 치킨 거리 문제 풀이를 마치도록 하겠습니다.
감사합니다!!
'Algorithm' 카테고리의 다른 글
| [Algorithm] SW 기출문제 - 나무 재테크(16235) 자바 풀이 (0) | 2023.05.10 |
|---|---|
| [Algorithm] SW 기출문제 - 인구 이동(16234) 자바 풀이 (2) | 2023.05.10 |
| [Algorithm] SW 기출문제 - 드래곤 커브(15685) 자바 풀이 (0) | 2023.05.09 |
| [Algorithm] SW 기출문제 - 사다리 조작(15684) 자바 풀이 (0) | 2023.05.08 |
| [Algorithm] SW 기출문제 - 감시(15683) 자바 풀이 (2) | 2023.05.08 |
