Java/코딩테스트
백준 15686
Bubbles
2023. 4. 6. 13:24
https://www.acmicpc.net/problem/15686
15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
🍺 메인로직
치킨 집 중 1개씩 고르기(isSelected[i] = true), 고르는 로직 반복 -> 최종 m개가 되면 거리 count -> 각 count 받아서 계속 answer과 비교해서 count로 갱신 -> 정답 출력
🍺 필요한 변수들
static ArrayList<Pos> home;
static ArrayList<Pos> store;
static boolean[] isSelected;
static int n, m, answer;
// answer는 Integer.MAX_VALUE로 초기화
좌표 클래스도 정의해두었다.
public static class Pos {
int x;
int y;
Pos (int x, int y) {
this.x = x;
this.y = y;
}
}
🍺 메서드
- 메인 : 데이터 입력받기, 위의 정적 변수들 초기화, combination(0,0) 수행 , 결과 출력
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
home = new ArrayList<>();
store = new ArrayList<>();
answer = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int temp = Integer.parseInt(st.nextToken());
if (temp == 1) {
home.add(new Pos(i, j));
}
else if (temp == 2) {
store.add(new Pos(i, j));
}
}
}
isSelected = new boolean[store.size()];
combination(0, 0);
System.out.println(answer);
}
- countDis (Pos home, Pos chicken) : 장소 사이 거리 계산
public static int countDis(Pos home, Pos chicken) {
return Math.abs(home.x - chicken.x) + Math.abs(home.y - chicken.y);
}
- combination(int cur, int count) : cur은 현재 몇 번 인덱스까지 뽑혔는지, count는 몇개 뽑았는지. count==m이 되면 chickenDistance()함수 수행
public static void combination(int cur, int chickenNum) {
// 다 뽑은 상태라면 각 집별로 치킨집과의 거리 계산
if (chickenNum == m) {
answer = Math.min(answer, chickenDistance());
return;
}
for (int i = cur; i < store.size(); i++) {
isSelected[i] = true;
combination(i+1, chickenNum+1);
// 재귀가 끝나면 다시 false
isSelected[i] = false;
}
}
- chickenDistance() : 현재 뽑힌 치킨집들로 모든 집과의 치킨거리 countDis() -> 최솟값들만 더해서 치킨거리 리턴
public static int chickenDistance() {
int result = 0; // 현재 뽑힌 치킨집들로 모든 집과의 치킨 거리를 잰 최솟값의 합
for (int i = 0; i < home.size(); i++) {
int temp = Integer.MAX_VALUE; // temp가 한 집당 모든 치킨집과의 거리를 재는 용
for (int j = 0; j < store.size(); j++) {
if (isSelected[j]) {
temp = Math.min(temp, countDis(home.get(i), store.get(j)));
}
}
result += temp;
}
return result;
}