[백준] 15686번 - "치킨 배달" (Java)
https://www.acmicpc.net/problem/15686
난이도 : 골드5
삼성 역량 테스트 기출문제입니다. 완전탐색과 DFS로 해결할 수 있는 문제지만, 문제를 정확히 읽는 것이 중요할 것 같습니다. 도시의 치킨 거리가 모든 집의 치킨 거리인 줄 몰랐습니다. 괜한 곳에 시간을 많이 썼네요.
아래와 같은 로직으로 문제를 설계했습니다.
1. 치킨집과 집을 저장할 자료 구조를 만든다.
2. 치킨집을 완전 탐색한다. (DFS, 백트래킹)
3. depth가 m을 만나면 각 집을 기준으로 치킨 거리를 구한다.
4. 치킨 거리의 합을 통해 도시 치킨 거리를 구한 후, answer의 최솟값을 구한다.(비교)
- Class Dot { }
집과 치킨집의 좌표를 저장할 객체입니다.
- static int map[][], n,m, answer;
주어진 입력과 필요한 변수를 전역적으로 설정하여 모든 함수에서 사용할 수 있도록 했습니다.
- static ArrayList<Dot> chicken, house;
이중 배열에서 치킨 집과 집을 ArrayList에 저장할 수 있도록 했습니다. 이들 또한 전역적으로 사용했습니다. 이들을 활용하여 완전 탐색을 진행합니다.
- static Stack<Dot> select;
chicken List를 탐색하며 m만큼 선택할 치킨 집을 Stack으로 설정하여 저장하도록 하였습니다.
- void main()
각 변수를 초기화 및 입력을 받습니다. map 순회하며 치킨 집과 집을 구분합니다. 구분된 값을 ArrayList에 저장합니다.
그 후 DFS 탐색을 위하여 selectChicken 함수를 호출합니다.
- void selectChicken(int start, int depth)
치킨집을 주어진 입력 m 만큼 탐색하기 위해 완전 탐색을 진행하는 함수입니다. m만큼 탐색되면 각 집마다 치킨 거리를 구한 후, 이 값을 통하여 도시의 치킨 거리를 구합니다.
- int getDistance(int r1, int c1, int r2, int c2)
문제의 조건에 따라서 거리를 구하는 함수입니다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
// BOJ / 15686번 / 치킨 배달 / 완전 탐색,구현, 자료구조 / 골드5
static int map[][];
static int n,m, answer;
static ArrayList<Dot> chicken, house;
static Stack<Dot> select;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
n = Integer.parseInt(stk.nextToken());
m = Integer.parseInt(stk.nextToken());
chicken = new ArrayList<>(); // 치킨집
house = new ArrayList<>(); // 집
map = new int[n][n];
answer = Integer.MAX_VALUE;
select = new Stack<>(); // 선택된 치킨집
for(int i=0; i<n; i++) {
stk = new StringTokenizer(br.readLine(), " ");
for(int j=0; j<n; j++) {
map[i][j] = Integer.parseInt(stk.nextToken());
if(map[i][j] == 1) {
house.add(new Dot(i, j));
}
else if(map[i][j] == 2) {
chicken.add(new Dot(i, j));
}
}
}
selectChicken(0, 0);
System.out.println(answer);
}
// 조합을 통해 치킨집 완전 탐색
public static void selectChicken(int start, int depth) {
if(depth == m) {
int sum = 0;
// 각 집마다 치킨 거리를 구한 후 도시 치킨 거리의 합을 구한다.
for(int i=0; i<house.size(); i++) {
int r1 = house.get(i).r;
int c1 = house.get(i).c;
int min = Integer.MAX_VALUE;
for(Dot s : select) {
int r2 = s.r;
int c2 = s.c;
min = Math.min(min, getDistance(r1,c1,r2,c2));
}
sum += min;
}
answer = Math.min(answer, sum);
return;
}
for(int i=start; i<chicken.size(); i++) {
select.push(new Dot(chicken.get(i).r, chicken.get(i).c));
selectChicken(i+1, depth+1);
select.pop();
}
}
public static int getDistance(int r1, int c1, int r2, int c2) {
return Math.abs(r1-r2) + Math.abs(c1-c2);
}
}
class Dot {
int r, c;
public Dot(int r, int c) {
this.r=r;
this.c=c;
}
}
피드백 환영합니다.
'문제 풀이 > Java' 카테고리의 다른 글
[백준] 16918번 - "봄버맨" (Java) (0) | 2022.01.03 |
---|---|
[백준] 1913번 - "달팽이" (Java) (0) | 2021.12.26 |
[백준] 11404번 - "플로이드" (Java) (0) | 2021.09.19 |
[프로그래머스] 위클리 챌린지(7주차) - "입실 퇴실" (Java) (0) | 2021.09.18 |
[프로그래머스] 위클리 챌린지(6주차) - "복서 정렬하기" (Java) (0) | 2021.09.17 |
댓글
이 글 공유하기
다른 글
-
[백준] 16918번 - "봄버맨" (Java)
[백준] 16918번 - "봄버맨" (Java)
2022.01.03 -
[백준] 1913번 - "달팽이" (Java)
[백준] 1913번 - "달팽이" (Java)
2021.12.26 -
[백준] 11404번 - "플로이드" (Java)
[백준] 11404번 - "플로이드" (Java)
2021.09.19 -
[프로그래머스] 위클리 챌린지(7주차) - "입실 퇴실" (Java)
[프로그래머스] 위클리 챌린지(7주차) - "입실 퇴실" (Java)
2021.09.18