문제

BOJ 15686: 치킨 배달 https://www.acmicpc.net/problem/15686

풀이

조건

• 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.
  • 치킨 거리는 가정집과 가장 가까운 치킨집 사이의 거리이다.
• 도시에 있는 치킨집 중에서 최대 M개를 고르고 나머지 치킨집은 제거한다.
• 어떻게 치킨 집을 남겨놓아야 도시의 치킨 거리가 가장 작게 될 지 구한다.

풀이 순서

• 입력을 받을 때
  • 치킨집 위치를 chickList에 넣는다.
  • 가정집 위치를 homeList에 넣는다.
• 백트래킹을 사용해 남겨놓을 치킨집 조합을 구한다.
  • for문을 사용해 남겨 놓을 치킨집 갯수를 다르게 한다.
  • chick[] 배열에 새롭게 조합한 치킨집을 넣는다.
  • 종료 조건에서 BFS를 사용해 치킨 거리를 구한다.
  • 동시에 모든 치킨집에서 최소거리를 구해야 하므로 모두 Queue에 넣고 탐색을 시작한다.
• 도시의 치킨 거리의 최솟값을 구한다.
• 아래의 코드에서 main() -> bt() -> bfs() 순으로 주석을 읽으면 이해가 쉽다.

코드

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

public class Main {
	
	static int N, M;
	static int[][] map;
	static Pos[] chick; // 치킨집 조합 넣을 배열
	static boolean[] isCheckedChick; // 치킨집 조합 만들 때 쓸 방문 배열
	static ArrayList<Pos> chickList = new ArrayList<>(); // 치킨집 위치 넣음
	static ArrayList<Pos> homeList = new ArrayList<>(); // 가정집 위치 넣음
	static Queue<Pos> que; // bfs에 쓸 큐
	static int[] dx = {0, 0, 1, -1};
	static int[] dy = {1, -1, 0, 0};
	static int min = 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());
		
		map = new int[N][N];
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 2) { // 치킨집 위치를 리스트에 넣음
					chickList.add(new Pos(i, j, 0));
				} else if(map[i][j] == 1) { // 가정집 위치를 리스트에 넣음
					homeList.add(new Pos(i, j));
				}
			}
		}
		
		chick = new Pos[chickList.size()]; // 치킨집 조합 넣을 배열
		isCheckedChick = new boolean[chickList.size()]; // 치킨집 조합 만들 때 쓸 체크 배열
		
		// 치킨집이 몇 개 남을 지 정해줌
		for(int i=1; i<=M; i++) {
			bt(i, 0, 0);
		}
		
		System.out.println(min);
		
	}
	
	// 치킨집에서 각 위치 거리값 구하기
	static void bfs(int[][] newMap, Queue<Pos> que, boolean[][] isVisitedQue) {
		/*
		 * newMap: 새롭게 조합 된 치킨집을 반영할 배열
		 * que: bfs에 사용할 큐
		 * isVisitedQue: bfs에 사용할 방문체크 배열
		 */
		// bt 메소드에서 조합된 치킨집을 미리 que에 모두 넣어놨고 방문 처리를 해줬기 때문에 바로 탐색을 시작한다
		while(!que.isEmpty()) {
			Pos p = que.poll();
			
			int curX = p.x;
			int curY = p.y;
			
			for(int t=0; t<4; t++) {
				int nx = curX + dx[t];
				int ny = curY + dy[t];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
				
				if(!isVisitedQue[nx][ny] && newMap[nx][ny] == 0) {
					que.add(new Pos(nx, ny, p.cnt + 1));
					isVisitedQue[nx][ny] = true;
					// 탐색한 위치의 값을 그 이전 값 + 1을 해 넣어준다.
					// 해당 값이 치킨 거리이다
					newMap[nx][ny] = p.cnt + 1;
				}
			}
			
			
		}
		
	}
	
	// 백트래킹으로 치킨집 조합 구함
	static void bt(int length, int depth, int start) {
		/*
		 * length: 치킨집 갯수
		 * depth: 종료 조건
		 * start: 이미 넣은 치킨집을 제외할 때 쓸 변수
		 */
		if(depth == length) {
			int sum = 0;
			
			int[][] newMap = new int[N][N]; // 새롭게 조합 된 치킨집을 반영할 배열
			
			Queue<Pos> que = new LinkedList<>(); // bfs에 사용할 큐
			boolean[][] isVisitedQue = new boolean[N][N]; // bfs에 사용할 방문체크 배열
			
			for(int i=0; i<length; i++) {
				// 치킨집에서 동시에 최소거리를 구할 것이기 때문에 미리 큐에 다 넣어놓는다.
				que.add(chick[i]);
				isVisitedQue[chick[i].x][chick[i].y] = true;
				// 새로운 배열에서 치킨집은 2로 표시한다.
				newMap[chick[i].x][chick[i].y] = 2;
			}
			// bfs를 사용해 newMap 의 각 위치에 치킨집과의 거리를 구해 넣는다
			bfs(newMap, que, isVisitedQue);
			// 가정집의 위치에 있는 값이 해당 가정집과 치킨집과의 거리이다
			for(int i=0; i<homeList.size(); i++) {
				Pos p = homeList.get(i);
				sum += newMap[p.x][p.y]; // 치킨 거리를 모두 더한다
			}
			
			min = Math.min(sum, min); // 최솟값을 구한다
			
			return;
		}
		
		for(int i=start; i<chickList.size(); i++) {
			if(!isCheckedChick[i]) {
				isCheckedChick[i] = true;
				//chickenList 에서 치킨집을 가져와 조합한다
				chick[depth] = chickList.get(i);
				bt(length, depth + 1, i);
				
				isCheckedChick[i] = false;
			}
		}
		
	}
	
	static class Pos{
		int x, y;
		int cnt;
		
		Pos(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		Pos(int x, int y, int cnt){
			this.x = x;
			this.y = y;
			this.cnt = cnt;
		}
	}
	
}

정리

• 치킨 가게 중 최대 M개를 골라야 하는데 이 조건을 빼고 풀이 했다가 시간을 조금 낭비했다.
• BFS를 쓰지 않고 조합된 치킨집과 가정집의 거리만 구하면 더 효율적으로 해결할 수 있다.