[백준] 15686번: 치킨 배달
21171 단어 알고리즘BacktrackingDFSJavaBacktracking
📝문제
끝까지 시간복잡도에 의심을 가지게 했던 문제...
과연 이렇게 푸는게 시간초과가 나지 않는 적절한 코드일까에 대해 생각했지만 이 방법 밖에 떠오르지가 않았다.
Combination(dfs + backtracking)으로 치킨집을 선택하고,
선택된 치킨집을 기준으로 각 집의 치킨 거리를 계산한다.
📌코드
package DFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ15686 {
/**
* dfs와 backtracking을 사용해서 풀자
*/
static int n, m;
static int[][] town;
static ArrayList<int[]> chicken;
static ArrayList<int[]> house;
static boolean[] isOpen;
static int answer = Integer.MAX_VALUE;
static void dfs(int cur, int cnt){
// 치킨집이 m개 열려있을 때
if(cnt == m){
int[] dist = new int[house.size()]; // 각 집의 치킨거리
Arrays.fill(dist, Integer.MAX_VALUE);
for(int i = 0; i < chicken.size(); i++){
if(!isOpen[i]) continue; // 닫혀 있는 치킨집은 패스
int[] curChicken = chicken.get(i);
for(int j = 0; j < house.size(); j++){
int[] curHouse = house.get(j);
dist[j] = Math.min(dist[j],
(Math.abs(curChicken[0] - curHouse[0]) + Math.abs(curChicken[1] - curHouse[1])));
}
}
// sum chicken distance
int sum = 0;
for(int i : dist){
sum += i;
}
answer = Math.min(answer, sum);
return;
}
// backtracking
for(int i = cur; i < chicken.size(); i++){
isOpen[i] = true;
dfs(i+1, cnt+1);
isOpen[i] = false;
}
}
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());
town = new int[n+1][n+1];
chicken = new ArrayList<>();
house = new ArrayList<>();
for(int i = 1; i < n+1; i++){
st = new StringTokenizer(br.readLine());
for(int j = 1; j < n+1; j++){
town[i][j] = Integer.parseInt(st.nextToken());
// 치킨집의 위치를 저장
if(town[i][j] == 2) chicken.add(new int[]{i, j});
else if(town[i][j] == 1) house.add(new int[]{i, j});
}
}
isOpen = new boolean[chicken.size()]; // 치킨집의 오픈 여부
dfs(0, 0);
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준] 15686번: 치킨 배달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@paulus0617/boj15686
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
package DFS;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ15686 {
/**
* dfs와 backtracking을 사용해서 풀자
*/
static int n, m;
static int[][] town;
static ArrayList<int[]> chicken;
static ArrayList<int[]> house;
static boolean[] isOpen;
static int answer = Integer.MAX_VALUE;
static void dfs(int cur, int cnt){
// 치킨집이 m개 열려있을 때
if(cnt == m){
int[] dist = new int[house.size()]; // 각 집의 치킨거리
Arrays.fill(dist, Integer.MAX_VALUE);
for(int i = 0; i < chicken.size(); i++){
if(!isOpen[i]) continue; // 닫혀 있는 치킨집은 패스
int[] curChicken = chicken.get(i);
for(int j = 0; j < house.size(); j++){
int[] curHouse = house.get(j);
dist[j] = Math.min(dist[j],
(Math.abs(curChicken[0] - curHouse[0]) + Math.abs(curChicken[1] - curHouse[1])));
}
}
// sum chicken distance
int sum = 0;
for(int i : dist){
sum += i;
}
answer = Math.min(answer, sum);
return;
}
// backtracking
for(int i = cur; i < chicken.size(); i++){
isOpen[i] = true;
dfs(i+1, cnt+1);
isOpen[i] = false;
}
}
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());
town = new int[n+1][n+1];
chicken = new ArrayList<>();
house = new ArrayList<>();
for(int i = 1; i < n+1; i++){
st = new StringTokenizer(br.readLine());
for(int j = 1; j < n+1; j++){
town[i][j] = Integer.parseInt(st.nextToken());
// 치킨집의 위치를 저장
if(town[i][j] == 2) chicken.add(new int[]{i, j});
else if(town[i][j] == 1) house.add(new int[]{i, j});
}
}
isOpen = new boolean[chicken.size()]; // 치킨집의 오픈 여부
dfs(0, 0);
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준] 15686번: 치킨 배달), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@paulus0617/boj15686저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)