백준 - 시뮬레이션 15686번 치킨 배달 / 오답

처음 접근한 풀이

 

구현만 해보자! 라는 생각으로 접근한BFS와 DFS를 이용한 풀이

import java.io.*;
import java.util.*;

public class Main {
    public static int n, m; // n: 크기, m: 최대 치킨 집 개수
    public static int min = Integer.MAX_VALUE;
    public static int[] resultMin;
    public static int[][] arr;
    public static int[][] house;
    public static boolean[][] visit;
    public static Queue<int[]> q = new LinkedList<>();


    public static void main(String[] args) throws IOException {
        // 0: 빈 칸, 1: 집, 2: 치킨집
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n + 1][n + 1];
        visit = new boolean[n + 1][n + 1];
        int index = 0;
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 1) {
                    index++;
                }
            }
        }
        house = new int[index][2];
        resultMin = new int[index];
        Arrays.fill(resultMin, Integer.MAX_VALUE);
        int count = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (arr[i][j] == 1) {
                    house[count][0] = i;
                    house[count][1] = j;
                    count++;
                }
            }
        }

        // for (int i = 0; i < index; i++) {
        //     for (int j = 0; j < 2; j++) {
        //         System.out.print("house : " + house[i][j]);    
        //     }
        //     System.out.println();
        // }

        dfs(0);
        if (min != Integer.MAX_VALUE) {
            System.out.println(min);
        } else {
            int ans = 0;
            for (int i : resultMin) {
                ans += i;
            }

            System.out.println(ans);
        }


    }

    public static void dfs(int depth) {
        if (depth == m) {
            if (m == 1) {
                findMin();
            } else {
                bfs();
            }
            return;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (!visit[i][j] && arr[i][j] == 2) {
                    visit[i][j] = true;
                    q.offer(new int[]{i, j});
                    dfs(depth + 1);
                    q.poll();
                    visit[i][j] = false;
                }
            }
        }
    }

    public static void bfs() {
        Queue<int[]> copy = q;

        while (!copy.isEmpty()) {
            int answer = 0;
            int[] nowLocation = copy.poll();
            int nowY = nowLocation[0];
            int nowX = nowLocation[1];

            for (int i = 0; i < house.length; i++) {
                int result = 0;
                result = Math.abs(house[i][0] - nowY) + Math.abs(house[i][1] - nowX);
                resultMin[i] = Math.min(result, resultMin[i]);
            }
        }
    }


    public static void findMin() {
        Queue<int[]> copy = q;

        while (!copy.isEmpty()) {
            int answer = 0;
            int[] nowLocation = copy.poll();
            int nowY = nowLocation[0];
            int nowX = nowLocation[1];

            for (int i = 0; i < house.length; i++) {
                int result = 0;
                result = Math.abs(house[i][0] - nowY) + Math.abs(house[i][1] - nowX);
                answer += result;

            }
            min = Math.min(answer, min);
        }
    }
}

시간 초과로 틀렸음..

3시간 이상을 사용해서 구현했기 때문에

다른 사람의 풀이를 참고해서 풀어봤다.

 

단순하게 DFS와 백트래킹으로만 해결할 수 있었다.

 

= 정답 코드 =

 

// "static void main" must be defined in a public class.
import java.io.*;
import java.util.*;

public class Main {
    public static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static int n, m; // n: 크기, m: 최대 치킨 집 개수
    public static int[][] arr;
    public static ArrayList<Point> house = new ArrayList<>();
    public static ArrayList<Point> chicken = new ArrayList<>();
    public static int ans;
    public static boolean[] visit;


    public static void main(String[] args) throws IOException {
        // 0: 빈 칸, 1: 집, 2: 치킨집
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        arr = new int[n][n];
        visit = new boolean[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());

                if (arr[i][j] == 1) {
                    house.add(new Point(i, j));
                } else if (arr[i][j] == 2) {
                    chicken.add(new Point(i, j));
                }
            }
        }

        ans = Integer.MAX_VALUE;
        visit = new boolean[chicken.size()];

        dfs(0, 0);
        System.out.println(ans);

    }

    public static void dfs(int depth, int start) {
        if (depth == m) {
            int result = 0;

            for (int i = 0; i < house.size(); i++) {
                int temp = Integer.MAX_VALUE;

                for (int j = 0; j < chicken.size(); j++) {
                    if (visit[j]) {
                        int resultX = Math.abs(house.get(i).x - chicken.get(j).x);
                        int resultY = Math.abs(house.get(i).y - chicken.get(j).y);
                        int distance = resultY + resultX;

                        temp = Math.min(distance, temp);
                    }
                }
                result += temp;
            }
            ans = Math.min(ans, result);
            return;
        }

        for (int i = start; i < chicken.size(); i++) {
            if (!visit[i]) {
                visit[i] = true;
                dfs(depth + 1, i);
                visit[i] = false;
            }
        }
    }
}