[백준] 15686번 - "치킨 배달" (Java)

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

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

www.acmicpc.net

---

 

난이도 :  골드5

 

 삼성 역량 테스트 기출문제입니다. 완전탐색과 DFS로 해결할 수 있는 문제지만,  문제를 정확히 읽는 것이 중요할 것 같습니다. 도시의 치킨 거리가 모든 집의 치킨 거리인 줄 몰랐습니다. 괜한 곳에 시간을 많이 썼네요.

 

 아래와 같은 로직으로 문제를 설계했습니다. 

 

1. 치킨집과 집을 저장할 자료 구조를 만든다. 

2. 치킨집을 완전 탐색한다. (DFS, 백트래킹)

3. depth가 m을 만나면 각 집을 기준으로 치킨 거리를 구한다. 

4. 치킨 거리의 합을 통해 도시 치킨 거리를 구한 후, answer의 최솟값을 구한다.(비교)

 

 

 

- Class Dot { }

 집과 치킨집의 좌표를 저장할 객체입니다. 

 

 

 

- static int map[][], n,m, answer;

 주어진 입력과 필요한 변수를 전역적으로 설정하여 모든 함수에서 사용할 수 있도록 했습니다. 

 

 

 

- static ArrayList<Dot> chicken, house;

 이중 배열에서 치킨 집과 집을 ArrayList에 저장할 수 있도록 했습니다. 이들 또한 전역적으로 사용했습니다. 이들을 활용하여 완전 탐색을 진행합니다. 

 

 

 

- static Stack<Dot> select;

 chicken List를 탐색하며 m만큼 선택할 치킨 집을 Stack으로 설정하여 저장하도록 하였습니다.  

 

 

 

- void main()

 각 변수를 초기화 및 입력을 받습니다. map 순회하며 치킨 집과 집을 구분합니다. 구분된 값을 ArrayList에 저장합니다. 

그 후 DFS 탐색을 위하여 selectChicken 함수를 호출합니다. 

 

 

 

- void selectChicken(int start, int depth)

 치킨집을 주어진 입력 m 만큼 탐색하기 위해 완전 탐색을 진행하는 함수입니다. m만큼 탐색되면 각 집마다 치킨 거리를 구한 후, 이 값을 통하여 도시의 치킨 거리를 구합니다.  

 

 

 

 

- int getDistance(int r1, int c1, int r2, int c2)

 문제의 조건에 따라서 거리를 구하는 함수입니다. 

 

 

 

  코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Main {
	// BOJ / 15686번 / 치킨 배달 / 완전 탐색,구현, 자료구조 / 골드5
	static int map[][];
	static int n,m, answer;
	static ArrayList<Dot> chicken, house;
	static Stack<Dot> select;
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(stk.nextToken());
		m = Integer.parseInt(stk.nextToken());
		
		chicken = new ArrayList<>(); // 치킨집
		house = new ArrayList<>(); // 집 	
		map = new int[n][n];
		answer = Integer.MAX_VALUE;
		select = new Stack<>(); // 선택된 치킨집
		
		for(int i=0; i<n; i++) {
			stk = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<n; j++) {
				map[i][j] = Integer.parseInt(stk.nextToken());
				if(map[i][j] == 1) {
					house.add(new Dot(i, j));
				}
				else if(map[i][j] == 2) {
					chicken.add(new Dot(i, j));
				}
			}
		}
		selectChicken(0, 0);
		System.out.println(answer);
	}
	// 조합을 통해 치킨집 완전 탐색 
	public static void selectChicken(int start, int depth) {
		
		if(depth == m) {
			int sum = 0;
			// 각 집마다 치킨 거리를 구한 후 도시 치킨 거리의 합을 구한다. 
			for(int i=0; i<house.size(); i++) {
				int r1 = house.get(i).r;
				int c1 = house.get(i).c;
				int min = Integer.MAX_VALUE;
				for(Dot s : select) {
					int r2 = s.r;
					int c2 = s.c;
					min = Math.min(min, getDistance(r1,c1,r2,c2));
				}
				sum += min;
			}
			answer = Math.min(answer, sum);
			return;
		}
		
		for(int i=start; i<chicken.size(); i++) {
			select.push(new Dot(chicken.get(i).r, chicken.get(i).c));
			selectChicken(i+1, depth+1);
			select.pop();
		}
	}
	
	public static int getDistance(int r1, int c1, int r2, int c2) {
		return Math.abs(r1-r2) + Math.abs(c1-c2);
	}
}
 
class Dot {
	int r, c;
	public Dot(int r, int c) {
		this.r=r;
		this.c=c;
	}
}

 

 

 

피드백 환영합니다.