[Java]백준 BaekJoon.AC 15686 : 치킨 배달 (브루트포스, Dot)

 

 

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

15686번: 치킨 배달

 

 

 

이번에도 실패할 걸 알면서 꿋꿋이 코드를 작성했더랬다...

혹시나 했는데 역시나 시간초과...!!ㅎㅎ

시간 줄이는 걸 항상 염두하고 있지만 쉽진 않다..

 

<틀린코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static boolean[] visit;
	static ArrayList<Chicken> store = new ArrayList<Chicken>();
	static Deque<Chicken> deque = new LinkedList<>();
	static Queue<House> home = new LinkedList<>();
	static int mns = 100000;
	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());
		
	
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if(num==2) {
					store.add(new Chicken(i, j));
				}else if(num==1) {
					home.add(new House(i, j));
				}
			}
		}
		
		visit = new boolean[store.size()];
		
		pick(1);
		
		System.out.println(mns);
	
	}
	
	public static void pick(int m) {
		
		if(m>M) {
			return;
		}
		

		for(int i=0; i<store.size(); i++) {
				
			if(visit[i]==true) continue;
			
			deque.add(store.get(i));
			visit[i] = true;
			
			if(m==deque.size()) {
				cal();
				pick(m+1);
				deque.pollLast();
				visit[i] = false;
			}
		}
			
	}
	
	public static void cal() {
		
		int total = 0;
		for(House house : home) {
			int road = 100000;
			
			int HC = house.col;
			int HR = house.row;
			
			for(Chicken chicken : deque) {
				int CC = chicken.col;
				int CR = chicken.row;
				
				road = Math.min(road, Math.abs(HC-CC)+Math.abs(HR-CR));
			}
			total = total + road;
		}
		
		mns = Math.min(mns, total);

	}
	
}

class Chicken{
	int col;
	int row;
	
	Chicken(int col, int row){
		this.col = col;
		this.row = row;
	}
}

class House{
	int col;
	int row;
	
	House(int col, int row){
		this.col = col;
		this.row = row;
	}
}

 

난 아무리 고쳐도 시간초과인데...ㅠ 이유도 모르겠다..

<틀린코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static boolean[] visit;
	static ArrayList<Dot> store = new ArrayList<Dot>();
	static ArrayList<Dot> home = new ArrayList<>();
	static int mns = Integer.MAX_VALUE;
	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());
		
	
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if(num==0) {
					continue;
				}else if(num==2) {
					store.add(new Dot(i, j));
				}else if(num==1) {
					home.add(new Dot(i, j));
				}
			}
		}
		
		visit = new boolean[store.size()];
		
		pick(1);
		
		System.out.println(mns);
	
	}
	
	public static void pick(int m) {
		
		if(m>M) {
			int total = 0;
			
			for(Dot house : home) {
				int road = Integer.MAX_VALUE;

				for(int i=0; i<visit.length; i++) {
					if(visit[i]==true) {
						
						road = Math.min(road, Math.abs(house.col-store.get(i).col)+Math.abs(house.row-store.get(i).row));
					}
				}
				
				total = total + road;
				if(total>mns) {
					return;
				}
			}	
		
			mns = Math.min(mns, total);
			return;
		}
		
		for(int i=0; i<store.size(); i++) {
			if(visit[i]==false) {
				visit[i] = true;
				pick(m+1);
				visit[i] = false;
			}
		}
			
	}
}

class Dot{
	int col;
	int row;
	
	Dot(int col, int row){
		this.col = col;
		this.row = row;
	}
}

 

방식은 얼추 맞았다는 것에 의의를 두자...!

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int N, M, ans = Integer.MAX_VALUE;
    static boolean[] visit;
    static List<int[]> home, chicken;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        home = new ArrayList<>();
        chicken = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                switch (sc.nextInt()) {
                    case 1:
                        home.add(new int[]{i, j});
                        break;
                    case 2:
                        chicken.add(new int[]{i, j});
                        break;
                }
        }
        visit = new boolean[chicken.size()];
        pick(-1, 0);

        System.out.println(ans);
    }

    static void pick(int start, int num) {
        if (num == M) {
            int total = 0;

            for (int[] h : home) {
                int road = Integer.MAX_VALUE;
                
                for (int i = 0; i < visit.length; i++) {
                    if (visit[i])
                    	road = Math.min(road, Math.abs(h[0] - chicken.get(i)[0]) + Math.abs(h[1] - chicken.get(i)[1]));
                }
                total = total + road;
            }
            ans = Math.min(ans, total);
            return;
        }

        for (int i=start+1; i<visit.length; i++) {
        	visit[i] = true;
        	pick(i, num+1);
            visit[i] = false;
        }
    }
}