백준 15686 치킨 배달 - 삼성 SW 역량 테스트 기출

백준 15686 치킨 배달 - 삼성 SW 역량 테스트 기출

1. 문제 링크

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

15686번: 치킨 배달

 

2. 문제 해결에 대한 아이디어

1. 0개부터 M(최대 남길 수 있는 치킨집)개 까지의 모든 경우를 확인하는 완전 탐색이다.

2. 치킨 집(c)과 집(h)의 거리는 |c.y - h.y| + |c.x - h.x|

2. 어떤 집의 치킨 거리는 가장 가까운 치킨 집과의 거리이다.

3. 각 케이스마다 치킨 거리의 합을 구하여 그 중 최솟값을 출력한다.

 

3. 코드

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

public class Main {

	static class Pair {
		int y, x;

		public Pair(int y, int x) {
			super();
			this.y = y;
			this.x = x;
		}

	}

	static int N, M;
	static int[][] board;
	static ArrayList<Pair> chickens = new ArrayList<>();
	static ArrayList<Pair> houses = new ArrayList<>();
	static ArrayList<Pair> candi = new ArrayList<>();
	static int answer = Integer.MAX_VALUE; // 최솟값

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] nm = br.readLine().split(" ");
		N = Integer.parseInt(nm[0]);
		M = Integer.parseInt(nm[1]); // 치킨 집의 갯수

		board = new int[N][N];
		for (int i = 0; i < N; i++) {
			String[] line = br.readLine().split(" ");
			for (int j = 0; j < N; j++) {
				board[i][j] = Integer.parseInt(line[j]);
				if (board[i][j] == 2)
					chickens.add(new Pair(i, j));
				else if (board[i][j] == 1)
					houses.add(new Pair(i, j));
			}
		}
		while (M > 0) {
			select(0, 0);
			--M;
		}
		System.out.println(answer);

	}

	static void select(int index, int depth) {
		if (depth == M) {
			getDist();
			return;
		}

		for (int i = index; i < chickens.size(); i++) {
			candi.add(chickens.get(i));
			select(i + 1, depth + 1);
			candi.remove(candi.size() - 1);
		}
	}

	static void getDist() {
		int sum = 0;
		for (int i = 0; i < houses.size(); i++) {
			Pair h = houses.get(i);
			int temp = Integer.MAX_VALUE;
			for (int j = 0; j < candi.size(); j++) {
				Pair c = candi.get(j);
				int dist = Math.abs(h.y - c.y) + Math.abs(h.x - c.x);
				temp = Math.min(temp, dist);
			}
			sum += temp;
		}
		answer = Math.min(answer, sum);
	}
	
}

 

4. 채점 결과

 

5. 느낀 점

1. 집을 기준으로 치킨거리를 구한다.

2. 처음에 visit 배열을 만들어 치킨 거리를 기록하고 기록한 값을 찾아 더하는 것으로 구현했다.

3. 2번과 달리 각 집의 치킨거리를 바로 더해주는 것으로 수정하여 메모리와 실행 속도를 줄일 수 있었다.

   . 추가 구현 없이 원하는 기능을 수행할 수 있는지 판단해야겠다!!