[백준 15686] 치킨배달/ 자바 / 브루트 포스(그래프순회)

문제         

레벨: G5
알고리즘: 브루트 포스(그래프순회)
풀이시간: 1시간 
힌트 참조 유무: 유

https://www.acmicpc.net/problem/15686

 

1 번째 시도: 실패   

• 여느 BFS 문제랑 같다 생각하고 작성하였다

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
//String[] s = br.readLine().split(" ");
//Integer.parseInt(br.readLine());
//int N = Integer.parseInt(s[0]);


public class Main {

//    static Set<int[]> chicken = new HashSet<>();
    static int N;
    static int[][] arr;
    static int[] xx = {1, 0, 0, -1};
    static int[] yy = {0, 1, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");
        N = Integer.parseInt(s[0]);
        int K = Integer.parseInt(s[1]);

        arr = new int[N][N];
        for (int i = 0; i < N; i++) {
            String[] s1 = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(s1[j]);
            }
        }

        int answer = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1)
                    answer += bfs(i, j);
            }
        }

        System.out.println(answer);

    }

    private static int bfs(int y, int x) {
        boolean[][] visited = new boolean[N][N];
        Queue<int[]> q = new LinkedList<>();
        visited[y][x] = true;
        q.add(new int[]{x, y, 0});

        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int px = poll[0];
            int py = poll[1];
            int cnt = poll[2];

            if (arr[py][px] == 2) {
//                System.out.println(x+" "+y+" "+px+" "+py);
                return cnt;
            }
            for (int i = 0; i < 4; i++) {
                int ny = py + yy[i];
                int nx = px + xx[i];
                if (ny < 0 || ny >= N || nx < 0 || nx >= N)
                    continue;
                if (visited[ny][nx])
                    continue;
                visited[ny][nx] = true;
                q.add(new int[]{nx, ny, cnt + 1});
            }
        }

        return 0;
    }
}

• 결과는 실패
• 조건 하나를 빼먹었다. 
  • 선택된 치킨집의 개수는 M
• 이 조건을 어떻게 충족시켜야 할까
  • 나의 생각
    • 가까운 치킨집이 있음에도 불과하고 조건에 충족시키기 위해 먼 치킨집을 선택할 집을 골라야한다.
    • or
    • 집이 아니라 치킨집을 선정해야 한다.
    • 모르겠다. 
    • 피드백 Time

2 번째 시도: 성공  

• 정답은 내 접근법과 달랐다. 
  • 최단거리라고 해서 BFS로 접근 X
  • 입력받을 때 집 위치와 치킨집 위치 기억한다
  •  DFS/백트래킹으로 오픈한 M개의 치킨집 경우의 수를 구한다.
  • 각 경우의 수로 구한 모든 치킨집을 순회하며 사람마다 어떤 치킨 집이 제일 거리가 가까운지 구한다.
  • 위 단계에서 구한 각 집마다 최단거리를 더한 후 이전 답보다 작을 시 답에 저장한다.
  • 다른 경우의 수도 4~5단계를 반복한다.
• 위 방법은 시간복잡도가 큰 편이다. 가능한 이유는 N과 M이 작아서이다.
  • 주어진 입력범위가 작다면 전체탐색을 고려해보자. 
  • 통상적으로 1~2초 시간제한 안에 통과하려면 1~2억개의 작업이 안에 들어야 한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Point {
    int x;
    int y;

    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int N, M;
    static int[][] map;
    static ArrayList<Point> person;
    static ArrayList<Point> chicken;
    static int ans;
    static boolean[] open;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new int[N][N];
        person = new ArrayList<>();
        chicken = new ArrayList<>();

        // 미리 집과 치킨집에 해당하는 좌표를 ArrayList에 넣어 둠.
        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] == 1) {
                    person.add(new Point(i, j));
                } else if (map[i][j] == 2) {
                    chicken.add(new Point(i, j));
                }
            }
        }

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

        DFS(0, 0);
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

    public static void DFS(int start, int cnt) {
        if (cnt == M) {
            int res = 0;

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

                // 어떤 집과 치킨집 중 open한 치킨집의 모든 거리를 비교한다.
                // 그 중, 최소 거리를 구한다.
                for (int j = 0; j < chicken.size(); j++) {
                    if (open[j]) {
                        int distance = Math.abs(person.get(i).x - chicken.get(j).x)
                                + Math.abs(person.get(i).y - chicken.get(j).y);

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

        // 백트래킹
        for (int i = start; i < chicken.size(); i++) {
            open[i] = true;
            DFS(i + 1, cnt + 1);
            open[i] = false;
        }
    }

}