https://www.acmicpc.net/problem/2842
문제 요약
N x N 형태의 마을이 있으며, 우체국은 'P', 집은 'K', 목초지는 '.'로 나타낸다.
또한 각 위치에는 고도가 있다.
배달은 우체국에서 시작해서 모든 집을 거쳐야 한다. 이동은 가로, 세로, 대각선으로 가능하다.
모두 배달한 이후에는 우체국으로 돌아온다.
방문한 칸 중 고도가 가장 높은 곳과 낮은 곳의 차이를 피로도라고 하자.
배달을 성공적으로 수행할 수 있는 가장 작은 피로도를 구하여라.
마을의 한 변의 크기 N은 최대 50이다.
각 지역의 고도는 최대 100만이다.
문제 접근
이 문제는 투포인터와 BFS를 결합하여 문제를 해결할 수 있다.
투포인터를 사용하려면 일단 어레이를 만들고 정렬을 해야 한다.
고도가 여러 개 있으니 겹치는 고도가 있을 것이다. 그런데 겹치는 건 필요 없다.
우체국과 집의 고도를 고려해야 한다. 두 값의 min과 max를 사용한다.
left 포인터는 1부터 min까지, right 포인터는 max부터 끝까지 갈 수 있다.
- 고도 지도를 훑어서 고도 셋을 만든다(중복 제거 위함).
- 고도 셋으로 고도 배열을 만들고 정렬한다.
- 우체국과 집의 고도를 모두 모은 뒤, 거기서 최대와 최소값을 얻는다.
- left 포인터와 right를 포인터를 만들어서 left는 전체 지도의 가장 낮은 고도, right는 앞서 구한 최대값으로 설정한다.
- left와 right 사이의 고도만을 거쳐 모든 집에 도달할 수 있는지 확인한다.
이때 모든 집에 도달하였는지 여부는 BFS로 방문한 집의 개수를 카운트해서 판단한다.(입력 받을 때 전체 집의 개수 기록해야함)- 만약 방문할 수 없었다면 right를 올리면서 시도한다. 처음으로 방문할 수 있을 때 7을 따라 수행한다.
- 만약 방문할 수 있었다면 left를 한 index씩 올리면서 다시 시도한다. 처음으로 불가능해진 경우의 직전의 값을 기록한다.
- 다시 right를 증가시켜 6과 7를 반복한다.
- 모든 경우의 간격을 기록한 뒤, 최소 간격을 찾으면 그 값이 정답이다.
풀이
기본적인 아이디어는 다음과 같다.
- (정리 예정)
이를 구현한 코드는 다음과 같다.
import java.util.*;
import java.io.*;
public class Main {
static int N;
static char[][] map;
static int[][] heightMap;
static boolean[][] visited;
static int[] heightArray;
static int initialMax = 0;
static int initialMin = 1000000;
static int[] startPoint = new int[2];
static int totalHouse = 0;
static int[] dx = {0, 0, 1, -1, 1, -1, 1, -1};
static int[] dy = {1, -1, 0, 0, -1, 1, 1, -1};
static ArrayList<Integer> diffs;
// 입력 받기
public static void getInput() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
heightMap = new int[N][N];
visited = new boolean[N][N];
// map 받기
for (int i = 0; i < N; i++) {
String line = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = line.charAt(j);
if (map[i][j] == 'P') {
startPoint[0] = j;
startPoint[1] = i;
}
if (map[i][j] == 'K') {
totalHouse += 1;
}
}
}
// heightMap 받기
for (int y = 0; y < N; y++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int x = 0; x < N; x++) {
heightMap[y][x] = Integer.parseInt(st.nextToken());
}
}
// visited 초기화
for (int a = 0; a < N; a++) {
for (int b = 0; b < N; b++) {
visited[a][b] = false;
}
}
}
// 두 지도를 훑어서 집과 우체국의 최소 고도, 최대 고도를 얻기
public static void findInitialMinMax() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] == 'P' || map[i][j] == 'K') {
initialMax = Math.max(initialMax, heightMap[i][j]);
initialMin = Math.min(initialMin, heightMap[i][j]);
}
}
}
}
// 고도 지도를 이용해 중복 없는 정렬된 고도 배열을 얻기
public static void getSortedHeight() {
HashSet<Integer> heights = new HashSet<Integer>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
heights.add(heightMap[i][j]);
}
}
heightArray = new int[heights.size()];
int i = 0;
for (Integer num : heights) {
heightArray[i] = num;
i++;
}
Arrays.sort(heightArray);
}
// BFS를 이용해 두 사이의 간격으로 모든 집을 방문할 수 있었는지 확인하기
public static boolean isPossible(int minHeight, int maxHeight) {
int count = 0;
ArrayDeque<int[]> ad = new ArrayDeque<int[]>();
// visited 초기화
for (int a = 0; a < N; a++) {
for (int b = 0; b < N; b++) {
visited[a][b] = false;
}
}
int nowX = startPoint[0];
int nowY = startPoint[1];
int[] now = new int[] {nowX, nowY};
ad.add(now);
visited[nowY][nowX] = true;
while (ad.size() > 0) {
now = ad.poll();
nowX = now[0];
nowY = now[1];
if (map[nowY][nowX] == 'K') {
count += 1;
}
if (count == totalHouse) {
return true;
}
for (int i = 0; i < 8; i++) {
int nextX = nowX + dx[i];
int nextY = nowY + dy[i];
if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < N && !visited[nextY][nextX]) {
int nextHeight = heightMap[nextY][nextX];
if (nextHeight >= minHeight && nextHeight <= maxHeight) {
int[] next = new int[] {nextX, nextY};
ad.add(next);
visited[nextY][nextX] = true;
}
}
}
}
return false;
}
// left와 right를 움직이며 문제 풀기
public static void calDiff() {
int leftIdx = 0;
int rightIdx = 0;
diffs = new ArrayList<Integer>();
for (int i = 0; i < heightArray.length; i++) {
if (heightArray[i] == initialMax) {
rightIdx = i;
break;
}
}
while (true) {
if (isPossible(heightArray[leftIdx], heightArray[rightIdx])) {
int diff = heightArray[rightIdx] - heightArray[leftIdx];
diffs.add(diff);
// 가능한 상황인데, left가 끝에 도달하면 더 할 필요 없음
if (heightArray[leftIdx] == initialMin) {
return;
}
leftIdx++;
} else {
rightIdx++;
// 불가능한 상황인데, right가 끝에 도달하면 더 할 필요 없음
if (rightIdx >= heightArray.length) {
return;
}
}
}
}
public static void main(String[] args) throws IOException {
getInput();
findInitialMinMax();
getSortedHeight();
calDiff();
int tiredValue = Collections.min(diffs);
System.out.println(tiredValue);
}
}회고
틀렸던 이유 1
투포인터를 사용하지 않고 우선순위 큐 + BFS로 문제 해결을 시도했는데, 불필요한 경로로 가는 경우가 발생하여 피로도를 제대로 구할 수 없다.
그렇다고 각 경로마다 우선순위 큐와 visited 배열을 사용하기에는 문제가 너무 복잡해지고, 메모리가 부족해져서 매우 어려울 것 같다.
틀렸던 이유 2
지도의 좌표를 {X, Y}로 사용하는 경우와 {Y, X}로 사용하는 경우가 혼재되어서 틀렸다.
순서는 딱히 중요하지 않지만, 하나의 문제 내에서는 이를 통일해서 사용할 수 있도록 유의해야 한다.
