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

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

15686번: 치킨 배달

m == 치킨집의 개수가 됐을 때, 도시의 치킨 거리를 구해야 한다
폐업하는 지점은 dfs의 순열을 통해 탐색하자

도시의 치킨 거리는 모든 집의 위치에서 가장 가까운 치킨집의 거리를 합산하여 구하고,
이를 min과 비교하여 저장하자

혹은 브루트포스를 통해 집의 좌표와 모든 치킨집의 좌표를 비교해도 될 것이다
뭐가 더 효율적인지는 모르겠는데, 문제에선 부르트포스를 사용해 절댓값을 구하도록 유도하고 있다
문제에 따라 구현해 보자

(1차 시도)

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

class Main{
    static int m, n, min = Integer.MAX_VALUE;
	static int[][] map;
	
	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+1][n+1];
        int chicken = 0;
        
        for(int i = 1; i <= n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j = 1; j <= n; j++) {
        		map[i][j] = Integer.parseInt(st.nextToken());
        		if(map[i][j] == 2) chicken++;
        	}
        }
        
        dfs(chicken);
        
        System.out.println(min);
	}
	
	static void dfs(int chicken) {
		if(chicken == m) {
			int sum = 0;
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					if(map[i][j] == 1) {
						int row = i;
						int col = j;
						int digit = Integer.MAX_VALUE;
						
						for(int r = 1; r <= n; r++) {
							for(int c = 1; c <= n; c++) {
								if(map[r][c] == 2) {
									int diff = Math.abs(row - r) + Math.abs(col - c);
									digit = Math.min(digit, diff);
								}
							}
						}
						sum += digit;
					}
				}
			}
			min = Math.min(min, sum);
			return;
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(map[i][j] == 2) {
					map[i][j] = 0;
					dfs(chicken--);
					map[i][j] = 2;
				}
			}
		}
	}
}

역시 시간초과가 나온다
dfs에선 순열만 이용하고, 거리를 구하는 for문 두개를 제거하는 대신 bfs를 사용해 보자

 

(2차 시도)

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

class Main{
    static int m, n, min = Integer.MAX_VALUE;
	static int[][] map;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	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+1][n+1];
        int chicken = 0;
        
        for(int i = 1; i <= n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j = 1; j <= n; j++) {
        		map[i][j] = Integer.parseInt(st.nextToken());
        		if(map[i][j] == 2) chicken++;
        	}
        }
        
        dfs(chicken);
        
        System.out.println(min);
	}
	
	static void dfs(int chicken) {
		if(chicken == m) {
			int sum = 0;
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j <= n; j++) {
					if(map[i][j] == 1) {						
						int digit = bfs(i, j);						
						
						sum += digit;
					}
				}
			}
			min = Math.min(min, sum);
			return;
		}
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(map[i][j] == 2) {
					map[i][j] = 0;
					dfs(chicken--);
					map[i][j] = 2;
				}
			}
		}
	}
	
	static int bfs(int x, int y) {
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {x, y, 0});
		boolean[][] visit = new boolean[n+1][n+1];
		visit[x][y] = true;
		
		while(!q.isEmpty()) {
			int[] now = q.poll();
			
			if(map[now[0]][now[1]] == 2) {
				return now[2];
			}
			
			for(int i = 0; i < 4; i++) {
				int nx = now[0] + dx[i];
				int ny = now[1] + dy[i];
				
				if(nx < 0 || ny < 0 || nx > n || ny > n || visit[nx][ny]) continue;
				
				q.add(new int[] {nx, ny, now[2] + 1});
				visit[nx][ny] = true;
			}
		}
		
		return 0;
	}
}

똑같이 시간초과
해결 방법을 모르겠어서 풀이를 본다

(최종)

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

class Main{
    static int m, n, min = Integer.MAX_VALUE;
	static int[][] map;
	static boolean[] open;
	static List<int[]> house;
	static List<int[]> chicken;
	
	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+1][n+1];
        house = new ArrayList<>();
        chicken = new ArrayList<>();
        
        for(int i = 1; i <= n; i++) {
        	st = new StringTokenizer(br.readLine());
        	for(int j = 1; j <= n; j++) {
        		map[i][j] = Integer.parseInt(st.nextToken());
        		
        		if(map[i][j] == 1) {
        			house.add(new int[] {i, j});
        		}
        		else if(map[i][j] == 2) {
        			chicken.add(new int[] {i, j});
        		}
        	}
        }
        open = new boolean[chicken.size()];
        
        dfs(0, 0);
        
        System.out.println(min);
	}
	
	static void dfs(int cnt, int start) {
		if(cnt == m) {
			int sum = 0;
			for(int i = 0; i < house.size(); i++) {
				int[] people = house.get(i);
				int digit = Integer.MAX_VALUE;
				
				for(int j = 0; j < chicken.size(); j++) {
					if(open[j]) {
						int diff = Math.abs(people[0] - chicken.get(j)[0]) + Math.abs(people[1] - chicken.get(j)[1]);
						digit = Math.min(digit,  diff);
					}
				}
				sum += digit;
			}
			
			
			min = Math.min(min, sum);
			return;
		}
		
		for(int i = start; i < chicken.size(); i++) {
			open[i] = true;
			dfs(cnt + 1, i + 1);
			open[i] = false;
		}
	}
}

조금 더 간단하게 생각하여 집list 와 치킨집list를 생성하여 위치를 저장한다
boolean[] 을 통해여 치킨집을 오픈할 곳을 정하고,
그 개수가 m과 같아지면 집의 좌표와 치킨집list를 순회하여 거리를 구하고 갱신한다

처음에 이론만 가지고 내게 익숙한 코드로 구현하니 시간 초과가 나왔다
그 이후에 정답과 비교하다보니 오랫동안 의문으로 가졌던 부분을 해결할 시간이 온 것 같다
바로 dfs의 방문표시, 시작점에 대한 부분이다
내가 쓴 코드와 정답 코드를 비교해 보자

내 코드
for(int i = 0; i < chicken.size(); i++) {
if(!open[i]) {
open[i] = true;
dfs(cnt + 1);
open[i] = false;
}
}

정답 코드
for(int i = start; i < chicken.size(); i++) {
open[i] = true;
fs(cnt + 1, i + 1);
open[i] = false;
}

이 사소한 차이로 시간 초과와 정답이 갈렸다
내 코드는 흔히 순열이라 부르는 모든 순서 관계를 확인하는 코드이다
정답 코드는 순서와 상관없이 중복을 제거한 코드이다
예를들면 1,2,3 을 구했다면 이후에 2,1,3 이나 3,2,1 은 확인하지 않는다
정리하고 나니 이 문제에서 채택해야할 방법이 무엇인지,
내 코드가 얼마나 낭비가 있는 코드인지가 이해 됐다
오픈된 치킨집의 '조합'은 의미가 있지만, '순서' 는 의미가 없는 문제이기 때문에 정답이 갈린 것이다


시간 초과를 제외하면 단번에 정답을 받은 만큼, 기분이 나쁘지는 않다
또한 부족했던 개념을 큰 스트레스 없이 배울 수 있었다는 점에서 더욱 그렇다
하지만 문제에 따라 사소한 차이로 시간 복잡도를 줄일 아이디어를 떠올리는 것은 여전히 부족하다고 느낀다
집list, 치킨집list를 사용하여 for문의 범위를 줄이는 방법은 뇌에 정착하려면 시간이 필요할 것 같다

같은 방법을 다시 떠올릴 키워드를 정리해 보자면,
내가 반복적으로 해당 좌표에 접근해야 한다면, 그 좌표를 자료구조에 저장하고
그 자료구조를 순회하는 것으로 좌표에 접근하면 모든 배열을 순회할 필요가 없다 라고 정리할 수 있겠다