BOJ 2842 집배원 한상덕(Java)
문제 탐색하기
- 행렬로 나뉘어진 각 지역은 우체국은 ‘P’, 집은 ‘K’, 목초지는 ‘.’ 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.
- 매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다.
- 배달은 마을에 하나밖에 없는 우체국 ‘P’가 있는 곳에서 시작한다.
- 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다.
- 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.
- 배달하면서 방문한 칸 중 가장 높은 곳과 낮은 곳의 고도 차이를 피로도라고 한다.
- 가장 작은 피로도로 모든 집에 배달을 하려면 어떻게 해야 하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (2 ≤ N ≤ 50)
다음 N개 줄에는 마을을 나타내는 행렬이 주어진다. ‘P’는 한 번만 주어지며, ‘K’는 적어도 한 번 주어진다.
다음 N개 줄에는 행렬로 나뉘어진 지역의 고도가 행렬 형태로 주어진다. 고도는 1,000,000보다 작거나 같은 자연수이다.
출력 첫째 줄에 가장 작은 피로도를 출력한다.
코드 설계하기
구현 방법
- 데이터 구조 및 초기화
- 지도 정보(
map)와 고도 정보(height)를 2차원 배열로 저장 - 우체국 위치(
P)와 집 위치들(KList)을 Point 객체로 저장 - 고유한 고도 값들을 정렬된 리스트(
uniqueHeights)로 저장
- 지도 정보(
- 이진 탐색을 통한 최소 피로도 찾기
- 가능한 최소 피로도(
low)와 최대 피로도(high) 사이에서 이진 탐색 수행 - 각 중간값(
mid)에 대해 해당 피로도로 모든 집 배달이 가능한지 확인
- 가능한 최소 피로도(
- 피로도 검증 (isPossible)
- 고유한 고도 값들을 순회하며 가능한 고도 범위 탐색
- 각 범위에 대해 우체국이 포함되는지 확인
- 포함되는 경우 BFS를 통해 모든 집 방문 가능 여부 확인
- BFS 탐색
- 주어진 고도 범위 내에서만 이동 가능
- 8방향(수평, 수직, 대각선)으로 탐색
- 방문한 집의 개수를 카운트하여 모든 집 방문 여부 확인
시간 복잡도
- 이진 탐색: O(log(max_height - min_height))
- 피로도 검증 (isPossible): O(H) (H는 고유한 고도 값의 개수)
- BFS 탐색: O(N²) (N x N 크기의 지도에서 최악의 경우 모든 칸을 방문)
- 전체 시간 복잡도: O(H * N² * log(max_height - min_height))
여기서 H는 최대 N²가 될 수 있으므로, 최악의 경우 시간 복잡도는 O(N⁴ * log(max_height - min_height))가 된다.
정답 코드 (Java)
package pl;
import java.io.*;
import java.util.*;
public class b2842 {
private static int N;
private static int[][] height; // 고도 배열
private static char[][] map; // 지도 배열
private static Point P; // 우체국 위치
private static ArrayList<Point> KList = new ArrayList<>(); // 집 위치 리스트
private static List<Integer> uniqueHeights = new ArrayList<>(); // 고유한 고도 값 리스트 (정렬됨)
// 8방향 이동 (수평, 수직, 대각선)
private static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1};
private static int[] dy = {0, -1, 0, 1, -1, 1, -1, 1};
static class Point {
int y, x; // y 좌표, x 좌표 순서 유지
Point(int y, int x) {
this.y = y;
this.x = x;
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new char[N][N];
height = new int[N][N];
Set<Integer> heightSet = new HashSet<>(); // 중복 제거용 Set
// 지도 정보 입력 및 P, K 위치 저장
for (int i = 0; i < N; i++) {
String s = br.readLine();
for (int j = 0; j < N; j++) {
map[i][j] = s.charAt(j);
if (map[i][j] == 'P') {
P = new Point(i, j);
} else if (map[i][j] == 'K') {
KList.add(new Point(i, j));
}
}
}
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// 고도 정보 입력 및 고유 고도 추출, 전체 최소/최대 고도 계산
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
height[i][j] = Integer.parseInt(st.nextToken());
heightSet.add(height[i][j]); // Set에 추가하여 고유값만 저장
min = Math.min(min, height[i][j]);
max = Math.max(max, height[i][j]);
}
}
// Set의 고유 고도를 정렬된 리스트로 변환
uniqueHeights = new ArrayList<>(heightSet);
Collections.sort(uniqueHeights);
// 이진 탐색 수행하여 최소 피로도 찾기
int minFatigue = binarySearch(min, max);
bw.write(String.valueOf(minFatigue));
bw.flush();
bw.close();
br.close();
}
// 피로도에 대해 이진 탐색을 수행하여 최소 피로도를 반환한다.
private static int binarySearch(int min, int max) {
int low = 0; // 최소 피로도 가능 값
int high = max - min; // 최대 피로도 가능 값
int result = high; // 가능한 최소 피로도를 저장할 변수, 최댓값으로 초기화
while (low <= high) {
int mid = low + (high - low) / 2; // 현재 테스트할 피로도
// 현재 피로도로 모든 집 배달이 가능한지 확인
if (isPossible(mid)) {
result = mid; // 가능하다면 결과 업데이트
high = mid - 1;
} else {
// 불가능하다면 더 큰 피로도 필요
low = mid + 1;
}
}
return result;
}
// 주어진 피로도 내에서 우체국에서 출발하여 모든 집을 방문할 수 있는지 확인한다.
private static boolean isPossible(int diff) {
// 고유한 고도 값들을 순회하며 가능한 범위를 탐색
for (int min_h : uniqueHeights) {
int max_h = min_h + diff; // 현재 최소 고도에 대한 최대 고도 계산
// 시작점의 고도가 현재 범위 내에 있는지 확인
if (height[P.y][P.x] >= min_h && height[P.y][P.x] <= max_h) {
// 우체국이 범위 내에 있다면, 해당 범위로 BFS 수행
if (BFS(min_h, max_h)) {
return true; // BFS 성공 시
}
}
// 다음 고도로 넘어가서 계속 탐색
}
// 모든 시작점을 시도해도 성공 못하면 false 반환
return false;
}
// 주어진 고도 범위 내에서만 이동해 BFS를 수행하고,
// 모든 K 지점을 방문할 수 있는지 확인한다.
private static boolean BFS(int min_h, int max_h) {
Queue<Point> q = new LinkedList<>();
boolean[][] visited = new boolean[N][N];
int visitedKCount = 0; // 방문한 K 지점 개수
// 시작점(P) 처리
q.offer(P);
visited[P.y][P.x] = true;
while (!q.isEmpty()) {
Point current = q.poll();
// 모든 K를 이미 방문했다면 탐색 종료
if (visitedKCount == KList.size()) {
return true;
}
// 8방향 탐색
for (int i = 0; i < 8; i++) {
int ny = current.y + dy[i];
int nx = current.x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
if (visited[ny][nx]) continue;
if (height[ny][nx] < min_h || height[ny][nx] > max_h) continue;
// 모든 조건 통과 시
visited[ny][nx] = true;
q.offer(new Point(ny, nx));
if (map[ny][nx] == 'K') {
visitedKCount++;
}
}
}
// BFS 종료 후, 모든 K 지점을 방문했는지 최종 확인
return visitedKCount == KList.size();
}
}
Leave a comment