[backjoon]15686 치킨 배달 java

www.acmicpc.net/problem/15686

15686번: 치킨 배달

Gold 5

나의 경우엔 안 되는 상점의 조합을 구해서 풀었다.

안 되는 상점의 조합은 DFS, 백트래킹이용

상점을 이용한 최단 거리는 BFS를 풀려고 했지만 시간 초과가 나왔다.

그래서 DFS + 완전 탐색로 풀었더니 정답!

거리 구하는 부분에서 헤매지만 않았으면 더 잘 풀었을 문제 ㅠㅠ

 

package com.example.demo;

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

class Main {
	static int N, min;
	static int[][] map;
	static Dot[] tempArr;
	static boolean[] markedStore;
	static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
	static LinkedList<Dot> houses = new LinkedList<Dot>();
	static LinkedList<Dot> stores = new LinkedList<Dot>();
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st; 
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		int StoreCnt = Integer.parseInt(st.nextToken());
		map = new int[51][51];
		min = Integer.MAX_VALUE;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				int state = Integer.parseInt(st.nextToken());
				map[i][j] = state;
				if (state == 1) houses.add(new Dot(i, j));
				if (state == 2) stores.add(new Dot(i, j));
			}
		}
		markedStore = new boolean[13];
		tempArr = new Dot[13];
		int removeStoreCnt = stores.size() - StoreCnt;
		selectedStore(0, 0, removeStoreCnt);

		System.out.println(min);
	}
	
	public static void selectedStore(int curIndex, int startIndex, int removeStoreCnt) {
		
		if(removeStoreCnt <= curIndex) {
			//지워야할 스토어 0으로 처리
			for (int j = 0; j < removeStoreCnt; j++) {
				Dot cur = tempArr[j];
				map[cur.row][cur.col] = 0;
			}
			//집별로 최단 치킨집 찾기
			int totalDistance = 0;
			for (int i = 0; i < houses.size(); i++) {
				Dot house = houses.get(i);
				totalDistance += shortStore(house, map);
			}
			min = Math.min(min, totalDistance);
			
            //0으로 지운 스토어 2로 복구
			for (int j = 0; j < removeStoreCnt; j++) {
				Dot cur = tempArr[j];
				map[cur.row][cur.col] = 2;
			}
			return;
		}
		
		for (int i = startIndex; i < stores.size(); i++) {
			if(markedStore[i]) continue;
			markedStore[i] = true;
			tempArr[curIndex] = stores.get(i);
			selectedStore(curIndex+1, i+1, removeStoreCnt);
			markedStore[i] = false;
			
		}
	}
	//시간 초과 뜨는 메서드
	public static int shortStoreBFS(Dot house, int[][] curMap) {
		Queue<Dot> queue = new LinkedList<Dot>();
		boolean[][] marked = new boolean[51][51];
		queue.add(house);
		marked[house.row][house.col] = true;
		while(!queue.isEmpty()) {
			Dot d= queue.poll();
			for (int i = 0; i < 4; i++) {
				int nextR = d.row + dir[i][0];
				int nextC = d.col + dir[i][1];
				if(curMap[d.row][d.col] == 2) {
					int returnDistance = Math.abs(d.row - house.row)+Math.abs(d.col - house.col);
					return returnDistance;
				}
				if(nextR < 0 || nextC <0 || nextR >= N || nextC >=N) continue;
				if(marked[nextR][nextC])continue;
				marked[nextR][nextC] = true;
				queue.add(new Dot(nextR, nextC));
			}
		}
		
		return 0;
	}
	public static int shortStore(Dot house, int[][] curMap) {
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < 31; i++) {
			for (int j = 0; j < 31; j++) {
				if(curMap[i][j] == 2) {
					int returnDistance = 
                    	Math.abs(i - house.row)+Math.abs(j - house.col);
					result = Math.min(result, returnDistance);
				}
			}
		}
		return result;
	}
}
class Dot{
	int row;
	int col;
	
	Dot(int row, int col){
		this.row = row;
		this.col = col;
	}
}