https://www.acmicpc.net/problem/15686
[풀이과정]
선택된 M개의 치킨집으로 치킨 거리를 구해야 하는 거니까 M개를 골랐는데 시간초과가 났다.
for문에서 시작 인덱스를 i + 1로 해야 기존 탐색했던 부분을 건너뛰니까 불필요한 탐색시간을 줄일 수 있는데, start+1로 하는 실수를 했다. 변수 때문에 논리오류가 생기면 찾기 힘들어지니까 항상 한 번 더 생각하자.
[코드]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;
/*
N*N 도시, 0 : 빈칸, 1 : 집, 2 : 치킨집
치킨 거리 = 집과 가장 가까운 치킨집 사이의 거리
도시의 치킨 거리 = 모든 집의 치킨 거리의 합
거리 = |r1 - r2| + |c1 - c2|
치킨집 최대 M개 고르기
어떻게 골라야 도시의 치킨 거리가 가장 작게 될지 구하라
*/
public class Main{
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M, result;
static int[][] city;
static List<Location> house, chicken;
static class Location{
int row;
int column;
boolean possible;
public Location(int row, int column){
this.row = row;
this.column = column;
}
public int getRow(){
return this.row;
}
public int getColumn(){
return this.column;
}
public boolean getPossible(){
return possible;
}
public void setPossible(boolean possible){
this.possible = possible;
}
}
public static void main(String[] args) throws IOException{
init();
deleteChicken(0,0);
/*
[출력]
도시의 치킨 거리의 최솟값
*/
System.out.println(result);
}
static void init() throws IOException {
/*
[입력]
1. N, M (2 <= N <= 50, 1 <= M <= 13)
2~N. 도시 정보
*/
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
city = new int[N][N];
house = new ArrayList<>();
chicken = new LinkedList<>();
result = Integer.MAX_VALUE;
for(int r = 0; r < N; r++){
st = new StringTokenizer(br.readLine());
for(int c = 0; c < N; c++){
city[r][c] = Integer.parseInt(st.nextToken());
//1 : 집
if(city[r][c] == 1){
house.add(new Location(r, c));
}
//2 : 치킨집
else if(city[r][c] == 2){
chicken.add(new Location(r, c));
}
}
}
}
static void deleteChicken(int start, int depth){
//M개의 치킨집을 다 골랐으면
if(depth == M){
//도시 거리 계산하기
result = Math.min(result, getCityLength());
return;
}
for(int i = start; i < chicken.size(); i++){
Location location = chicken.get(i);
if(!location.getPossible()){
location.setPossible(true);
deleteChicken(i + 1, depth + 1);
location.setPossible(false);
}
}
}
static int getCityLength(){
int cityLength = 0;
for(Location houseLoc : house){
int chickenLength = Integer.MAX_VALUE;
for(Location chickenLoc : chicken){
if(!chickenLoc.getPossible()){
continue;
}
chickenLength = Math.min(chickenLength, getChickenLength(houseLoc, chickenLoc));
}
cityLength += chickenLength;
}
return cityLength;
}
//치킨거리
static int getChickenLength(Location house, Location chicken){
return Math.abs(house.getRow()-chicken.getRow()) + Math.abs(house.getColumn() - chicken.getColumn());
}
}
'백준 > 완전탐색' 카테고리의 다른 글
[백준] 1062 : 가르침 (JAVA) (0) | 2024.09.20 |
---|---|
[백준] 14500 : 테트로미노 (0) | 2023.04.10 |