백준 2842번 : 집배원 한상덕 [Java]

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

 

문제 탐색하기

평범한 bfs문제인 것처럼 보이긴 하지만 플래 4에 들어가 있는 이유가 있을 것이다. 얼핏 봐서는 최소힙 (우선순위큐)와 같은 것을 사용해서 방문할 곳 중 높이가 현재 최대 최소에 근접한 것을 뽑으면 될 것 같지만 그렇지 않다. 이미 방문한 노드의 다음 노드를 실시간으로 높이차를 계산해서 최적해를 보장할 방법이 없다. 이미 최소힙에 들어있는 것을 실시간으로 재조정 할 수가 없다. 결국에는 모든 높이의 구간을 탐색해봐야 하는 것이다. 그러면 어떤 식으로 탐색해 볼 수 있을까?

 

일단 너비 우선 탐색을 통해서 모든 K를 방문하는 경로를 계산 하는 방법은 맞다. 여기서 중요한 것은 높이차를 어디까지 허용할 지 계산 하는 방법인데, 이는 투 포인터를 통해서 구할 수 있다. 모든 높이를 중복없이 배열이나 리스트에 정렬하여서, 어떤 높이 범위까지 허용할지 매번 계산 하는 방식을 통해서 확인 할 수 있다. 예를 들어서 예제 2 번에서는 입력이 아래와 같다.

3
P..
.KK
...
3 2 4
7 4 2
2 3 1

 

이 때 모든 높이를 오름차순으로 정렬하고 중복을 없애보면 아래와 같은 배열을 얻을 수 있다.

[1, 2, 3, 4, 7]

 

이 배열을 투 포인터 알고리즘을 통해서 탐색하고 높이의 최솟값과 최대값을 bfs알고리즘에 넣어서 아래를 확인해보면 된다.

• P (우체국)이 방문 가능한지
• 모든 K (집)가 방문 가능한지 

이를 통해서 모든 조건을 만족한다면 답을 갱신하는 방식으로 정답을 구할 수 있다.

 

코드 구현하기

1. 입력을 처리하고, 지도, 높이, 방문을 기록할 2차원 배열을 만든다.
2. 모든 높이를 중복없이 포함하는 배열을 오름차순 정렬 하고 이를 투 포인터를 통해서 범위를 지정한다.
3. 위에서 지정한 범위를 통해서 너비 우선 탐색을 진행한다. bfs를 통해 아래 조건을 만족하는 지 확인하고 만족한다면 답을 갱신한다.
   1. P가 방문 가능한지 확인
   2. 모든 지점을 방문후 방문한 K의 갯수가 전체 K의 갯수가 같은 지 확인
4. 정답을 출력한다.

풀이

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

public class Main {
	static int N, sx, sy, totalHouse, answer = Integer.MAX_VALUE;
	static char[][] map;
	static boolean[][] visited;
	static int[][] height;
	static List<Integer> heights = new ArrayList<>();
	static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
	static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

	public static void main(String[] args) {
		FastReader fr = new FastReader();
		N = fr.nextInt();
		map = new char[N][N];
		height = new int[N][N];
		totalHouse = 0;

		TreeSet<Integer> heightSet = new TreeSet<>();

		for (int i = 0; i < N; i++) {
			String s = fr.next();
			for (int j = 0; j < N; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'P') {
					sx = i;
					sy = j;
				} else if (map[i][j] == 'K') {
					totalHouse++;
				}
			}
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				height[i][j] = fr.nextInt();
				heightSet.add(height[i][j]);
			}
		}

		heights.addAll(heightSet);

		int s = 0, e = 0;
		while (e < heights.size() && s < heights.size()) {
			if (bfs(heights.get(s), heights.get(e))) {
				answer = Math.min(answer, heights.get(e) - heights.get(s));
				s++;
			} else {
				e++;
			}
		}

		System.out.println(answer);
	}

	private static boolean bfs(int minHeight, int maxHeight) {
		if (height[sx][sy] < minHeight || height[sx][sy] > maxHeight) {
			return false;
		}

		visited = new boolean[N][N];
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[]{sx, sy});
		visited[sx][sy] = true;
		int count = 0;

		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int x = cur[0], y = cur[1];

			if (map[x][y] == 'K') {
				count++;
			}

			for (int i = 0; i < 8; i++) {
				int nx = x + dx[i], ny = y + dy[i];

				if (nx < 0 || ny < 0 || nx >= N || ny >= N || visited[nx][ny]) continue;
				if (height[nx][ny] < minHeight || height[nx][ny] > maxHeight) continue;

				visited[nx][ny] = true;
				q.add(new int[]{nx, ny});
			}
		}
		return count == totalHouse;
	}

	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}