Baekjoon[15686] - 치킨 배달

링크

15686번: 치킨 배달

문제설명

• 치킨집 중 M개만 남긴 상태들 중 거리연산의 합이 최소인 경우 구하기

문제풀이

• 치킨집의 개수를 K 개라 했을 때, KCM 조합.
• 거리 최소연산 구하기 - by 모든 경우 탐색

문제코드

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main15686_치킨_배달 {

    public static int[][] dir = {
            {-1,0},
            {1,0},
            {0,-1},
            {0,1}
    };

    public static int Ans = Integer.MAX_VALUE;
    public static int Temp;

    public static ArrayList<int[]> chicken = new ArrayList<int[]>();
    public static ArrayList<int[]> house = new ArrayList<int[]>();
    public static int[] selectedchicken;

    public static int N;
    public static int M;
    public static int K;
    public static int[][] map;
    public static boolean[][] visited;

//    public static int chickenlen_bfs(int[] rc) {
//        int len=0;
//        
//        boolean[][] visited = new boolean[N][N];
//        LinkedList<int[]> q = new LinkedList<int[]>();
//        q.add(rc);
//        visited[rc[0]][rc[1]]=true;
//        
//        int[] now;
//        int nr;
//        int nc;
//        
//        while(!q.isEmpty()) {
//            for (int i = 0, qsize = q.size(); i < qsize; i++) {
//                now = q.poll();
//                if(map[now[0]][now[1]]==2) {
//                    return len;
//                }
//                for (int d = 0; d < 4; d++) {
//                    nr = now[0] + dir[d][0];
//                    nc = now[1] + dir[d][1];
//                    if(nr>=0 && nr<N && nc>=0 && nc<N && !visited[nr][nc]) {
//                        q.add(new int[] {nr,nc});
//                        visited[nr][nc]=true;
//                    }
//                }
//            }
//            len++;
//        }
//        
//        return -1;
//    }

    public static int len(int[] a, int[] b) {
        return Math.abs(a[0]-b[0]) + Math.abs(a[1]-b[1]);
    }

    public static int chickenlen(int[] rc) {
        int len=Integer.MAX_VALUE;
        for (int i = 0; i < M; i++) {
            len = Math.min(len, len(rc,chicken.get(selectedchicken[i])));
        }
        return len;
    }

    public static void Search(int cnt,int next, int flag) {
        if(cnt==M) {
            Temp = 0;
            for (int[] h : house) {
                    if(Temp>Ans)return;
                    Temp+=chickenlen(h);
            }
            Ans = Math.min(Temp, Ans);
            return;
        }

//        chicken size K 중 M개 선택한 map 만들기
        for (int i = next; i < K; i++) {
            if((flag & (1<<i))==0) {
                selectedchicken[cnt]=i;
                Search(cnt+1, i+1, flag | (1<<i));
            }
        }
    }
//    permutation 13P6 = 1235520
//    combination 13C6 = 1716

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/baekjoon/15686.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==2) {
                    chicken.add(new int[] {i,j});
//                    map[i][j]=0;
                }
                else if(map[i][j]==1) {
                    house.add(new int[] {i,j});
                }
            }
        }

        K = chicken.size();
        selectedchicken = new int[M];

        Search(0,0,0);

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• KCM-Combination을 생각해놓고 KPM-Permutation으로 구현해서 터졌음

  • 13C13 = 1 << 13P13 = 13! = 6227020800
  • 13C6 = 1716 << 13P6 = 123520

• Combination 구현 시 next부터 고려하는걸 next+1부터 고려했음

  • for (int i = next; i < K; i++) {
     if((flag & (1<<i))==0) {
         selectedchicken[cnt]=i;
         Search(cnt+1, i+1, flag | (1<<i));
     }
    }

• 거리 구할때

  • BFS로 구현했었음

    • O(N^2)만큼 탐색이라 시간차이 큼

    • 

  • 완전탐색으로하면

    • O(M)만큼만 탐색하면 됨

    • 

잘한점

• 문제 이해하고 구현하는건 빨랐음
• KCM을 통한 맵 설치를 치킨집의 좌표를 저장해서 구현했음
• 집의 개수를 맵 탐색하면서 거리 계산 - > 집의 좌표를 저장해서 탐색할 수 있게 함
  • O(N^2) -> O(2N)