[BOJ] 백준 2842번 집배원 한상덕 (Java)

#2842 집배원 한상덕

난이도 : 플레 5

유형 : 투 포인터/ BFS

2842번: 집배원 한상덕

▸ 문제

상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.

매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.

상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌다. 상덕이가 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 하자. 이때, 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.

▸ 입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)

다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. 'P'는 한 번만 주어지며, 'K'는 적어도 한 번 주어진다.

다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다.

▸ 출력

첫째 줄에 가장 작은 피로도를 출력한다.

 

문제 풀이 

먼저 P에서 여러 개의 K지점을 방문하는 일은 BFS 너비 우선 탐색 알고리즘으로 풀이할 수 있다. 언덕의 오차를 최소로하기 위해 (bottom, up)의 경계를 정해놓고 무작정 대입해보면 답을 구할 수 있다.

 

그런데 고도의 최대는 100만이므로 무작정 대입하기에는 O(n^2)으로 시간초과가 발생한다. 그러므로 투포인터로 탐색 범위를 좁혀줘야 한다. 투 포인터는 S, E 두 개의 포인터를 사용하여 탐색하는 기법인데 최대 O(n)안에 탐색이 가능하다.

 

투 포인터 예시

 

데이터를 다 입력받은 후 투 포인터 탐색을 하기 위해 높이를 2차원 배열에서 1차원 자료구조로 바꿔준다. 그런 다음 정렬해서 언덕의 오차가 최소가 되는 구간을 찾아준다.

• 주의해야 될 점은 최솟값은 P의 언덕부분도 체킹해줘야 한다는 것이다. 그래서 미리 P와 K들 중 최솟값을 갖는 언덕을 찾고 바운드를 설정해준다.

Collections.sort(height);

int bottom = 0;
int up = height.indexOf(max);

int minIdx = height.indexOf(min); //P,K 중 가장 최소 언덕 높이. 최솟값을 넘을 필요 없다
int maxIdx = height.size();

int res = Integer.MAX_VALUE;
while(bottom <= minIdx && bottom <= up && up < maxIdx) {
	int l = height.get(bottom);
	int r = height.get(up);
	if(bfs(sx, sy, l, r, target) == 0) {
		res = Math.min(res, (r-l));
		bottom++;
	}else {
		up++;
	}
}
System.out.println(res);

 

 

풀이 코드 

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

public class Main {

	static int n;
	static char[][] map;
	static int[][] mapNum;
	static int[] dx = {-1, 1, 0, 0, 1, 1, -1, -1};
	static int[] dy = {0, 0, -1, 1, 1, -1, 1, -1};
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		
		int sx=0, sy=0, target=0;
		map = new char[n][n];
		for(int i=0; i<n; i++) {
			map[i] = br.readLine().toCharArray();
			for(int j=0; j<n; j++) {
				if(map[i][j] == 'P') {
					sx = j;
					sy = i;
				}else if(map[i][j] == 'K') {
					target++;
				}
			}
		}
		
		int max = -1, min = Integer.MAX_VALUE;
		List<Integer> height = new ArrayList<>();
		mapNum = new int[n][n];
		for(int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<n; j++) {
				mapNum[i][j] = Integer.parseInt(st.nextToken());
				height.add(mapNum[i][j]);
				if(map[i][j] == 'P' || map[i][j] =='K'){
					max = Math.max(max, mapNum[i][j]);
					min = Math.min(min, mapNum[i][j]);
				}
			}
		}
		
		Collections.sort(height);
		int bottom = 0;
		int up = height.indexOf(max);
		int minIdx = height.indexOf(min);
		int maxIdx = height.size();
		int res = Integer.MAX_VALUE;
		while(bottom <= minIdx && bottom <= up && up < maxIdx) {
			int l = height.get(bottom);
			int r = height.get(up);
			if(bfs(sx, sy, l, r, target) == 0) {
				res = Math.min(res, (r-l));
				bottom++;
			}else {
				up++;
			}
		}
		System.out.println(res);
	}
	
	static int bfs(int x, int y, int bottom, int up, int target) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][] check = new boolean[n][n];
		q.add(new int[]{x,y});
		check[y][x] = true;
		while(!q.isEmpty()) {
			int[] p = q.poll();
			int px = p[0], py = p[1];
		
			if(target == 0) return target;
			
			for(int d=0; d<8; d++) {
				int nx = px+dx[d];
				int ny = py+dy[d];
				
				if(nx < 0 || ny < 0 || nx > n-1 || ny > n-1) continue;
				if(check[ny][nx] || mapNum[ny][nx] < bottom || mapNum[ny][nx] > up) continue;
				
				check[ny][nx] = true;
				if(map[ny][nx] == 'K') {
					target--;
				}
				q.add(new int[] {nx,ny});
			}
		}
		return target;
	}
}