[알고리즘] 백준15686 치킨배달 - 자바

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

15686번: 치킨 배달

 

 

[풀이 코드]

package day0223;

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

public class BOJ_15686_치킨배달 {
	static int N, M;
	static int result = Integer.MAX_VALUE;
	static class Point {
		int y, x;

		Point(int y, int x) {
			this.y = y;
			this.x = x;
		}
	}

	static List<Point> home = new ArrayList<>();
	static List<Point> chicken = new ArrayList<>();
	static boolean[] visited;

	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());
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				int num = Integer.parseInt(st.nextToken());
				if (num == 1) {
					home.add(new Point(i, j));
				} else if (num == 2) {
					chicken.add(new Point(i, j));
				}
			}
		} // 집과 치킨집 따로 리스트에 담기 종료
		
		visited = new boolean[chicken.size()];
		dfs(0, 0);
		System.out.println(result);
	}

	static void dfs(int idx, int cnt) {
		if (idx == chicken.size()) { // 문제 좀 잘 읽자 진짜 개짜증나네
			if (cnt == M) { // 다풀고 뭐하는거야
				int dist = 0;
				for (int i = 0; i < home.size(); i++) {
					int htoc = Integer.MAX_VALUE;
					for (int j = 0; j <chicken.size(); j++) {
						if (visited[j]) {
							int hc = Math.abs(home.get(i).x - chicken.get(j).x)
									+ Math.abs(home.get(i).y - chicken.get(j).y);
							htoc = Math.min(htoc, hc);
						}
					}
					dist += htoc;
				} //거리비교for문
				result = Math.min(result, dist);
			} //cnt 조건
			return;
		}
		
		visited[idx] = true;
		dfs(idx + 1, cnt + 1);
		visited[idx] = false;
		dfs(idx + 1, cnt);
	}
	
}

• 문제의 예제 입력을 보고 DFS, BFS 탐색 문제겠지 싶었다... 하지만 조합 문제였고 로직은 그렇게 어렵지 않았다.
  
  
• 기저 조건을 설정해주는 부분에서 자꾸 헤매었는데 이건 문제를 제대로 안 읽어서 시간만 엄청 버렸다..!
  
  
• 이 문제의 포인트는 Point클래스를 활용해서 정점 관리를 해준 것인데 사실 그냥 new int [] {i, j} 이런 식으로 해도 된다. 하지만 자바니까 연습 중이다.
  
  
• 또 그래프로 입력을 받지만 ArrayList에 집과 치킨집을 따로 담아준다. 그리고 입력으로 주어지는 그래프에서 치킨집의 개수와 M은 다르다. 이걸 한참 후에 발견한 나는 틀려 마땅했다.