[JAVA] 백준 15686번 : 치킨 배달(삼성 SW 역량 테스트 기출 문제)

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

15686번: 치킨 배달

문제

DFS + 구현 문제이다. 처음 시간 초과나서 방법을 좀 바꿔서 다시 풀었다.

 

해결 방안

처음에는 전체 집List, 전체 치킨집List와 visited 배열을 사용하여 전체 치킨집 중 M개를 DFS 와 백트래킹을 이용하여 구현하였다. 
하지만 거리를 구하는 과정에서 전체 집에서 전체 치킨집을 돌면서 M개에 포함되지 않는 경우도 조건을 통해 거르다 보니 시간 초과가 났다.

그래서 다음에는 visited 배열을 빼고 선택된 치킨집List를 만들어 M개 만큼 선택된 치킨집 List를 만들어서 거리를 구하였더니 맞출 수 있었다.

나머지 부분은 크게 어렵지 않은 부분이여서 생략한다.

 

코드 (시간 초과)

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

// 치킨 배달
// NxN 도시
// 1x1 칸 (0:빈칸, 1:집, 2:치킨집)
// (r, c) r,c는 1부터 시작
// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
// 도시의 치킨 커리는 모든 집의 치킨 거리의 합
// 치킨집 갯수 M개

// M개 이외 치킨집 폐업, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램
public class Main {
	
	static int N; // 도시 크기 NxN(2~50)
	static int M; // 최대 치킨집 갯수(1~13)
	static int[][] map;

	static List<int[]> hList = new ArrayList<>(); // 전체 집 위치
	static List<int[]> cList = new ArrayList<>(); // 전체 치킨 집 위치
	static boolean[] visited;
	
	static int min = Integer.MAX_VALUE; // 가장 작은 도시의 치킨 거리
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		str = br.readLine();
		
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
		
		map = new int[N+1][N+1];
		
		StringTokenizer st;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=1; j<N+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				// 집 리스트
				if(map[i][j] == 1) {
					hList.add(new int[] {i, j});
				}
				// 치킨집 리스트
				else if(map[i][j] == 2) {
					cList.add(new int[] {i, j});
				}
			}
		}
		visited = new boolean[cList.size()];
		// ==== 입력 끝 =====
		
		dfs(0);
		
		System.out.println(min);

	}
	
	// 치킨집이 M만큼 있는 경우의 치킨 거리 탐색
	static void dfs(int depth) {
		// 치킨 집이 M만큼 있는 경우
		if(depth >= M) {
			int distanceSum = 0;
			
			int minDistance;
			int distance;
			// 각 집에서 M에 포함되는 치킨집들 중 가장 짧은 치킨 거리구하기
			for(int i=0; i<hList.size(); i++) {
				minDistance = Integer.MAX_VALUE;
				distance = 0;
				for(int j=0; j<cList.size(); j++) {
					// M에 포함된 치킨집
					if(visited[j]) {
						distance = Math.abs(hList.get(i)[0]-cList.get(j)[0]) + Math.abs(hList.get(i)[1]-cList.get(j)[1]);
						minDistance = Math.min(distance, minDistance);
					}
				}
				
				distanceSum += minDistance;
			}
			
			// 가장 작은 도시의 치킨 거리 구하기
			min = Math.min(min, distanceSum);
		}
		else {
			// M과 치킨집 갯수가 같으면 폐업되는 치킨 집 없음
			if(M == cList.size()) {
				for(int i=0; i<cList.size(); i++) {
					visited[i] = true;
				}
				dfs(M);
			}
			// list에서 치킨집 M만큼 고르기
			else {
				for(int i=0; i<cList.size(); i++) {
					if(!visited[i]) {
						visited[i] = true;
						dfs(depth+1);
						visited[i] = false;
					}
				}
			}
		}
	}

}

 

코드 (합격)

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

// 치킨 배달
// NxN 도시
// 1x1 칸 (0:빈칸, 1:집, 2:치킨집)
// (r, c) r,c는 1부터 시작
// 치킨 거리 : 집과 가장 가까운 치킨집 사이의 거리
// 도시의 치킨 커리는 모든 집의 치킨 거리의 합
// 치킨집 갯수 M개

// M개 이외 치킨집 폐업, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램
public class Main {
	
	static int N; // 도시 크기 NxN(2~50)
	static int M; // 최대 치킨집 갯수(1~13)
	static int[][] map;

	static List<int[]> hList = new ArrayList<>(); // 전체 집 위치
	static List<int[]> cList = new ArrayList<>(); // 전체 치킨 집 위치
	static List<int[]> selected = new ArrayList<>(); // 선택된 치킨집
	
	static int min = Integer.MAX_VALUE; // 가장 작은 도시의 치킨 거리
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String str;
		str = br.readLine();
		
		N = Integer.parseInt(str.split(" ")[0]);
		M = Integer.parseInt(str.split(" ")[1]);
	
		map = new int[N+1][N+1];
		
		StringTokenizer st;
		for(int i=1; i<N+1; i++) {
			str = br.readLine();
			st = new StringTokenizer(str, " ");
			for(int j=1; j<N+1; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
				// 집 리스트
				if(map[i][j] == 1) {
					hList.add(new int[] {i, j});
				}
				// 치킨집 리스트
				else if(map[i][j] == 2) {
					cList.add(new int[] {i, j});
				}
			}
		}
		// ==== 입력 끝 =====
		
		dfs(0,0);
		
		System.out.println(min);

	}
	
	// 치킨집이 M만큼 있는 경우의 치킨 거리 탐색
	static void dfs(int idx, int depth) {
		// 치킨 집을 M만큼 고른 경우
		if(depth >= M) {
			int distanceSum = 0;
			
			int minDistance;
			int distance;
			// 각 집에서 M에 포함되는 치킨집들 중 가장 짧은 치킨 거리구하기
			for(int i=0; i<hList.size(); i++) {
				minDistance = Integer.MAX_VALUE;
				distance = 0;
				for(int j=0; j<selected.size(); j++) {
					// M에 포함된 치킨집
					distance = Math.abs(hList.get(i)[0]-selected.get(j)[0]) + Math.abs(hList.get(i)[1]-selected.get(j)[1]);
					minDistance = Math.min(distance, minDistance);
					
				}
				distanceSum += minDistance;
			}
			
			// 가장 작은 도시의 치킨 거리 구하기
			min = Math.min(min, distanceSum);
		}
		else {
			
			// list에서 치킨집 M만큼 고르기
			for(int i=idx; i<cList.size(); i++) {
				selected.add(cList.get(i));
				dfs(i+1, depth+1);
				selected.remove(depth);
			}
			
		}
	}

}