백준_15686_치킨배달

소요시간 : 약 1시간 30분

 

필요 스킬 : 조합

수정 전 코드는 매우 안좋은 코드이다... 속도도 매우매우 느리고 메모리도 너무 많이 잡아먹었다.

보는 것과 같이 수정 전 코드는  2956ms 이라는 매우 꼬진? 코드이다.

수정 후 코드는 148ms로 거의 1/20로 줄였다.

<수정한 코드>

package net.acmicpc;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class boj_15686_치킨배달 {
    static int N, M, ans, tot;
    static int[] arr, pick;
    static ArrayList<int[]> chicken, home, open;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        if (st.hasMoreTokens()) {
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
        }
 
        chicken = new ArrayList<>();
        home = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            if (st.hasMoreTokens()) {
                for (int j = 0; j < N; j++) {
                    int x = Integer.parseInt(st.nextToken());
                    if (x == 2) {
                        chicken.add(new int[] { i, j });
                    }
                    if (x == 1) {
                        home.add(new int[] { i, j });
                    }
                }
            }
        }
        arr = new int[M];
        pick = new int[chicken.size()];
        ans = Integer.MAX_VALUE;
 
        for (int i = 0; i < chicken.size(); i++) {
            pick[i] = i;
        }
        combination(M, 0, 0);
        System.out.println(ans);
    }
 
    public static void combination(int m, int start, int cnt) {
        if (cnt == m) {
            open = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                int chickY = chicken.get(arr[i])[0];
                int chickX = chicken.get(arr[i])[1];
                open.add(new int[] { chickY, chickX });
            }
 
            find();
            if (tot < ans) {
                ans = tot;
            }
            return;
        }
 
        for (int i = start; i < chicken.size(); i++) {
            arr[cnt] = pick[i];
            combination(m, i + 1, cnt + 1);
        }
    }
 
    public static void find() {
        tot = 0;
        for (int i = 0; i < home.size(); i++) {
            int distance = Integer.MAX_VALUE;
            int[] h = home.get(i);
            for (int j = 0; j < open.size(); j++) {
                int[] c = open.get(j);
                distance = Math.min(distance, Math.abs(c[0] - h[0]) + Math.abs(c[1] - h[1]));
            }
            tot += distance;
        }
    }
}
 

 

 

<수정 전 코드>

package net.acmicpc;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
//약 1시간 30분 걸림.
public class boj_15686_치킨배달 {
    static int N, M, dist, ans;
    static int[] arr, pick;
    static int[][] map, count, cityMap;
    static boolean[][] visited;
    static int[] dy = { 0, -1, 0, 1 };
    static int[] dx = { 1, 0, -1, 0 };
    static ArrayList<int[]> chicken;
    static Queue<int[]> que;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        if (st.hasMoreTokens()) {
            N = Integer.parseInt(st.nextToken());
            M = Integer.parseInt(st.nextToken());
        }
        map = new int[N][N];
 
        int cntChicken = 0;
 
        chicken = new ArrayList<>();
 
        for (int i = 0; i < map.length; i++) {
            st = new StringTokenizer(br.readLine());
            if (st.hasMoreTokens()) {
                for (int j = 0; j < map[i].length; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    if (map[i][j] == 2) {
                        chicken.add(new int[] { i, j });
                    }
                }
            }
        }
        arr = new int[M];
        pick = new int[chicken.size()];
        ans = Integer.MAX_VALUE;
        for (int i = 0; i < chicken.size(); i++) {
            pick[i] = i;
        }
        combination(M, 0, 0);
        System.out.println(ans);
    }
 
    public static void combination(int m, int start, int cnt) {
        if (cnt == m) {
            cityMap = new int[N][N];
 
            for (int i = 0; i < arr.length; i++) {
                int chickY = chicken.get(arr[i])[0];
                int chickX = chicken.get(arr[i])[1];
                cityMap[chickY][chickX] = 3;
            }
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[i].length; j++) {
                    if (map[i][j] == 1) {
                        cityMap[i][j] = 1;
                    }
                }
            }
 
            bfs();
            if (dist < ans) {
                ans = dist;
            }
            return;
        }
 
        for (int i = start; i < chicken.size(); i++) {
            arr[cnt] = pick[i];
            combination(m, i + 1, cnt + 1);
        }
    }
 
    public static void bfs() {
        dist = 0;
        que = new LinkedList<>();
        for (int i = 0; i < cityMap.length; i++) {
            for (int j = 0; j < cityMap.length; j++) {
                que.clear();
                aa: if (cityMap[i][j] == 1) {
                    visited = new boolean[N][N];
                    count = new int[N][N];
                    que.offer(new int[] { i, j });
                    visited[i][j] = true;
                    while (!que.isEmpty()) {
                        int[] tmp = que.poll();
                        int cy = tmp[0];
                        int cx = tmp[1];
                        for (int d = 0; d < 4; d++) {
                            int ny = cy + dy[d];
                            int nx = cx + dx[d];
                            if (safe(ny, nx) && !visited[ny][nx]) {
                                count[ny][nx] = count[cy][cx] + 1;
                                visited[ny][nx] = true;
                                if (cityMap[ny][nx] == 3) {
                                    dist += count[ny][nx];
                                    break aa;
                                }
                                que.offer(new int[] { ny, nx });
                            }
                        }
                        if (dist >= ans) {
                            return;
                        }
                    }
                }
            }
        }
    }
 
    public static boolean safe(int y, int x) {
        if (y < N && x < N && y >= 0 && x >= 0) {
            return true;
        }
        return false;
    }
}