[BOJ] ์น˜ํ‚จ ๋ฐฐ๋‹ฌ(15686)

[๋ฐฑ์ค€(BOJ)] 15686_์น˜ํ‚จ ๋ฐฐ๋‹ฌ JAVA

๋ฌธ์ œ : BOJ_15686๋ฒˆ ์น˜ํ‚จ ๋ฐฐ๋‹ฌ

๋ฌธ์ œ ์„ค๋ช…

N*N ํฌ๊ธฐ์˜ map์—์„œ ์ง‘๊ณผ ์น˜ํ‚จ์ง‘์ด ์ฃผ์–ด์ง„๋‹ค.
์ตœ๋Œ€ m ๊ฐœ์˜ ์น˜ํ‚จ์ง‘์„ ์ œ์™ธํ•œ ๋‚˜๋จธ์ง€ ์น˜ํ‚จ์ง‘์„ ๋‹ค ์—†์• ์•ผ ํ•œ๋‹ค.
์ด๋•Œ ์ง‘๊ณผ ์น˜ํ‚จ์ง‘๊ณผ์˜ ์ตœ์†Œ ๊ฑฐ๋ฆฌ(์ˆ˜์ง๊ฑฐ๋ฆฌ์˜ ์ฐจ + ์ˆ˜ํ‰๊ฑฐ๋ฆฌ์˜ ์ฐจ)์˜ ํ•ฉ์˜ ์ตœ์†Ÿ๊ฐ’์„ ๊ตฌํ•ด์•ผ ํ•œ๋‹ค.


Solution

์™„์ „ ํƒ์ƒ‰(์กฐํ•ฉ)

N์˜ ์ตœ๋Œ€ ํฌ๊ธฐ๋Š” 50, M์˜ ์ตœ๋Œ€ ํฌ๊ธฐ๋Š” 13์ด๋‹ค.
13๊ฐœ์˜ ์น˜ํ‚จ์ง‘์—์„œ 7๊ฐœ์˜ ์น˜ํ‚จ์ง‘์„ ์„ ํƒํ•˜๋Š” ์กฐํ•ฉ์˜ ์ˆ˜๊ฐ€ ๊ฐ€์žฅ ํฌ๋ฏ€๋กœ ๋‹ค์Œ๊ณผ ๊ฐ™์ด ๊ณ„์‚ฐํ•ด๋ณด๋ฉด,

50 * 50(๋„์‹œ์˜ ์ตœ๋Œ€ ํฌ๊ธฐ) * 13C7 * 7(๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋งˆ๋‹ค 7๊ฐœ์˜ ์น˜ํ‚จ์ง‘๊ณผ ๊ฑฐ๋ฆฌ๋ฅผ ํ™•์ธํ•ด๋ด„) == 30,030,000

์ด๋ฏ€๋กœ ์กฐํ•ฉ์„ ์ด์šฉํ•œ ์™„์ „ ํƒ์ƒ‰์œผ๋กœ ํ•ด๊ฒฐ์ด ๊ฐ€๋Šฅํ•˜๋‹ค.


Description

  • ์กฐํ•ฉ์€ recursion์ด๋ž€ ๋ฉ”์†Œ๋“œ์—์„œ ์žฌ๊ท€๋กœ ์ง„ํ–‰ํ•˜์˜€๋‹ค.
  • ์ขŒํ‘œ๊ฐ’์€ Node๋ผ๋Š” ํด๋ž˜์Šค๋ฅผ ๋งŒ๋“ค์–ด์„œ x, y ๊ฐ’์„ ๋ฐ›์•˜๋‹ค.

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

class Node{
    private int x;
    private int y;
    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }

    public int getX() {
        return x;
    }

    public int getY() {
        return y;
    }
}

public class Main {

    public static int n;
    public static int m;
    public static int[] [] map;
    public static ArrayList<Node> chicken = new ArrayList<>();
    public static ArrayList<Node> house = new ArrayList<>();
    public static ArrayList<ArrayList<Integer>> combs = new ArrayList<ArrayList<Integer>>();
    public static boolean[] chk;

    public static int getDis(Node a, Node b){
        int result = 0;
        result+= Math.abs(a.getX() - b.getX());
        result+= Math.abs(a.getY() - b.getY());
        return  result;
    }


    public static void recursion(int idx, int cnt){
        if(cnt == m){
            ArrayList<Integer> arr = new ArrayList<>();
            for(int i=0; i<chk.length; i++){
                if(chk[i]) arr.add(i);
            }
            combs.add(arr);
            return;
        }

        for(int i = idx; i<chk.length; i++){
            if(chk[i]) continue;
            chk[i] = true;
            recursion(i,cnt+1);
            chk[i] = false;
        }

    }

    public static void main(String[] args) throws IOException {
        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+1][n+1];

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j]==1) house.add(new Node(i,j));
                else if(map[i][j]==2) chicken.add(new Node(i,j));
            }
        }
        chk = new boolean[chicken.size()];
        recursion(0,0);
        int res = (int)1e9;
        for(int i =0; i<combs.size();i++){
            int value = 0;
            for(int j=0; j<house.size();j++){
                Node houseNode = house.get(j);
                int temp = 0;
                for(int k=0;k<combs.get(i).size();k++){
                    Node chickenNode = chicken.get(combs.get(i).get(k));
                    int dist = getDis(houseNode, chickenNode);
                    if(k==0) temp = dist;
                    else temp = Math.min(dist,temp);
                }
                value += temp;
            }
            res = Math.min(res,value);
        }
        bw.write(String.valueOf(res)+"\n");
        bw.flush();
        br.close();
        bw.close();
    }
}