알고리즘/백준 문제 풀이
[BOJ] 15686. 치킨 배달
바켱서
2020. 8. 3. 18:27
https://www.acmicpc.net/problem/15686
접근 방법
입력 값에서 그냥 ArrayList에 집 and 치킨집을 넣어주었다.
그리고 치킨집에 대해서는 아직 개장을 한지 안한지에 대해서 state 필드를 주었다.
그리고 치킨집을 하나 고를 때 마다 문제에서 원했던 ' 치킨 거리 ' 를 구하고 답에 계속 최소인지 확인하면서 대입을 해주었다.
주의 사항
치킨 집을 하나씩 넣어줄 때 (0,1) (2,0) 은 (2,0) (0,1) 은 중복이 된다. 이 중복을 없애자.
또한 for(int i=start; i<chickenLoc.size(); i++) 여기에서 i = start를 하지 않으면 안된다!!!
이 의미에 대해서는 곰곰히 생각하고 왜 불필요한지에 대해서 이해를 하면 될 것 같다.
static void getAllDistance(int start, int cnt, int bit){ if(cnt == M){ visit[bit] = true; // printChickenLoc(); int temp = getCityChickenDistance(); // System.out.println(" -> distance : " + temp + " and bit is " + bit); ans = Math.min(temp, ans); } for(int i=start; i<chickenLoc.size(); i++){ if(chickenLoc.get(i).state || visit[bit|1<<i]) continue; chickenLoc.get(i).state = true; getAllDistance(i,cnt+1, bit|1<<i); chickenLoc.get(i).state = false; } }
Need Know
- 구현!
전체 코드 ( Java )
import java.io.*;
import java.util.*;
class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static int N;
static int M;
static int[][] map;
static ArrayList<Location> chickenLoc;
static ArrayList<Location> homeLoc;
static final int HOME = 1;
static final int CHICKEN = 2;
static int ans = Integer.MAX_VALUE;
static boolean[] visit;
public static void main(String[] args) throws IOException {
set();
solve();
bw.flush();
bw.close();
br.close();
}
static void set() throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][N];
chickenLoc = new ArrayList<>();
homeLoc = new ArrayList<>();
for(int i=0;i<N; i++){
st = new StringTokenizer(br.readLine());
for(int k=0; k<N;k++){
map[i][k] = Integer.parseInt(st.nextToken());
if(map[i][k] == CHICKEN) {
chickenLoc.add(new Location(i,k,false));
}
if(map[i][k] == HOME){
homeLoc.add(new Location(i,k));
}
}
}
visit = new boolean[1<<13+1];
}
static void printChickenLoc(){
for(int i=0; i<chickenLoc.size(); i++){
if(chickenLoc.get(i).state){
System.out.print("(" +chickenLoc.get(i).x + "," + chickenLoc.get(i).y +")"+" ");
}
}
}
static void printAllChickenLoc(){
for(int i=0; i<chickenLoc.size(); i++){
System.out.print("(" +chickenLoc.get(i).x + "," + chickenLoc.get(i).y +")"+" ");
}
}
static void solve() throws IOException {
// printAllChickenLoc();
if(chickenLoc.size()==M){
// 모두 개장 시키자!
for(int i=0; i<chickenLoc.size(); i++){
chickenLoc.get(i).state = true;
}
ans = getCityChickenDistance();
}else{
getAllDistance(0,0,0);
}
bw.write(ans + "");
}
static void getAllDistance(int start, int cnt, int bit){
if(cnt == M){
visit[bit] = true;
// printChickenLoc();
int temp = getCityChickenDistance();
// System.out.println(" -> distance : " + temp + " and bit is " + bit);
ans = Math.min(temp, ans);
}
for(int i=start; i<chickenLoc.size(); i++){
if(chickenLoc.get(i).state || visit[bit|1<<i]) continue;
chickenLoc.get(i).state = true;
getAllDistance(i,cnt+1, bit|1<<i);
chickenLoc.get(i).state = false;
}
}
static int getCityChickenDistance(){
int cityChickenDistance = 0;
for(int i=0; i<homeLoc.size(); i++){
cityChickenDistance += getChickenDistance(homeLoc.get(i));
}
return cityChickenDistance;
}
static int getDistance(int x1, int y1, int x2, int y2){
return (Math.abs(x1-x2)+Math.abs(y1-y2));
}
static int getChickenDistance(Location homeLoc){
int chickenDistance = Integer.MAX_VALUE;
for(int i=0; i<chickenLoc.size(); i++){
// 개장 되어 있는 치킨집에 대해서만 구하기
if(chickenLoc.get(i).state) {
int distance = getDistance(homeLoc.x, homeLoc.y, chickenLoc.get(i).x, chickenLoc.get(i).y);
if (chickenDistance > distance) chickenDistance = distance;
}
}
return chickenDistance;
}
}
class Location{
int x,y;
boolean state;
public Location(int x, int y) {
this.x = x;
this.y = y;
}
public Location(int x, int y, boolean state) {
this.x = x;
this.y = y;
this.state = state;
}
}