치킨 배달(BJ_15686)

1. 문제 링크

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

 

 

---

 

2. 나의 코드

메모리: 18120 kb
시간: 184 ms
코드 길이: 1977 B
시간 복잡도 : O(2^C * HC)
설명
- 조합 알고리즘 사용
- 완전 탐색

import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BJ_15686 {

    static List<Point> houses;
    static List<Point> chickens;
    static int[][] map;
    static Point[] input;
    static int N, M, result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        houses = new ArrayList<Point>();
        chickens = new ArrayList<Point>();
        map = new int[N][N];
        input = new Point[M];
        result = Integer.MAX_VALUE;

        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) houses.add(new Point(i, j));
                else if (map[i][j] == 2) chickens.add(new Point(i, j));
            }
        }

        comb(0, 0);
        System.out.println(result);
    }

    public static void comb(int cnt, int start) {

        if (cnt == M) {
            int sumDist = 0;
            for (Point house : houses) {
                int minDist = Integer.MAX_VALUE;
                for (Point chicken : input) {
                    int dist = Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y);
                    minDist = Math.min(minDist, dist);
                }
                sumDist += minDist;
            }
            result = Math.min(sumDist, result);
            return;
        }

        for (int i = start; i < chickens.size(); i++) {
            input[cnt] = chickens.get(i);
            comb(cnt + 1, i + 1);
        }
    }
}

 

---

 

3. 정답 코드

import java.util.*;
 
public class Main {
 
    static int n, m;
    static int[][] board;
    static int min = Integer.MAX_VALUE;
    static ArrayList<Node> chickenList = new ArrayList<>(); //치킨집 위치를 저장하는 리스트 
    static ArrayList<Node> houseList = new ArrayList<>(); // 집의 위치를 저장하는 리스트
    static boolean[] chickenVisited; // 뽑은 치킨집 체크
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        m = scan.nextInt();
        
        board = new int[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = scan.nextInt();
                if(board[i][j] == 1) houseList.add(new Node(i, j));
                else if(board[i][j] == 2) chickenList.add(new Node(i, j));
            }
        }
        
        chickenVisited = new boolean[chickenList.size()];
        backtracking(0, 0); //m개의 치킨집을 뽑는다.
        System.out.println(min);
    }
    
    public static void backtracking(int count, int idx) {
        if(count == m) { //치킨 거리의 최솟값을 구한다.
            int total = 0; // 도시의 치킨거리
            for(int i = 0; i < houseList.size(); i++) {
                int sum = Integer.MAX_VALUE;
                for(int j = 0; j < chickenList.size(); j++) {
                    if(chickenVisited[j] == true) { //i번째 집에서부터 j번짜 치킨집 까지의 거리 중 최소값을 구한다.
                        int dist = Math.abs(houseList.get(i).x - chickenList.get(j).x) 
                                + Math.abs(houseList.get(i).y - chickenList.get(j).y);
                        sum = Math.min(sum, dist);
                    }
                }
                total += sum;
            }
            min = Math.min(total, min);
            return;
        }
        
        for(int i = idx; i < chickenList.size(); i++) {
            if(chickenVisited[i] == false) {
                chickenVisited[i] = true;
                backtracking(count + 1, i + 1);
                chickenVisited[i] = false;
            }
        }
    }
    
    public static class Node {
        int x;
        int y;
        
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

 

---

 

4. 배운 점

- 완전 탐색으로 풀 수 있는 경우는 완탐으로 풀자.

- 순열과 조합은 제대로 공부하자