[백준 2842번 집배원 한상덕] JAVA 풀이

Last Update: 2022-03-13

문제의 요구사항

  • 문제 링크
    P에서 출발해서 모든 K를 방문하고 P로 돌아오는 방법중 가장 적은 피로도로 움직이는 방법을 구하는 문제이다.
    이때 주의할점이 있다.
  1. 모든 K를 방문하는것만 구현하면 된다. 같은 길로 돌아가면 되기 때문
  2. 부분 문제의 최적이 전체문제의 최적이 아니다.

주의할 점 2번을 깨닫는게 좀 어려웠던것 같다.
한상덕의 피로도는 전체 경로중에 가장 높은 고도와 가장 낮은 고도의 차이이며 이를 최소화하는것이 이 문제의 목표이다.

즉, DFS로 한상덕의 마을을 탐색한다고 했을때, 부분적인 경로에서 피로도를 최소화하는것으로는 문제해결이 불가능하다는 것 이다.

따라서 전체 경로에 대한 가장 낮은고도와 가장 높은 고도를 설정해 놓고, 이 고도사이에서 모든 집을 방문할 수 있는가를 확인하는것이 풀이방법이 될 것 이다.

대략적인 방법

1. 전체 경로의 고도 특정하기
입력을 통해 마을의 모든 부분의 고도를 확인할 수 있는데 이를 중복을 제거하고 오름차순으로 정렬한다.
이 정렬된 고도값들에 두개의 포인터(left, right 등)를 사용하여 고도값을 조정한다.
```java while(left <= right && right < 고도값개수){ …//left와 right이용해 최대, 최소 고도를 우체국에서 출발하는 dfs에 전달하기 if(dfs결과방문한집개수 == 전체집개수){ right = Math.min(result, altitute[right] - altitute[left]); left++; }else right++; }

__2. DFS 구현하기__  
DFS메서드의 인자는 `최대고도`, `최소고도`, `현재위치`를 가지도록 했고, 
리턴값은 해당 부분경로에서 방문한 집의 개수로 했다.

java int dfs(int low, int high, int h, int w){ //1. 기저조건(이미 방문했거나 지도의 범위를 벗어난경우 0리턴)

//2. 탐색하기(갈 수 있는 부분경로들의 결과값을 모두 합침)

//3. 리턴

}

## 소스코드

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

public class 집배원_한상덕 {

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

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    N = Integer.parseInt(br.readLine());

    board = new char[N][];
    altitute = new int[N][N];
    //중복을 제거하기위해 Set사용함
    HashSet<Integer> alts = new HashSet<Integer>();

    for(int h = 0; h < N; h++){
        board[h] = br.readLine().toCharArray();
        for(int w = 0; w < N; w++){
            if(board[h][w] == 'P'){ph = h; pw = w;}
            else if(board[h][w] == 'K'){K++;}
        }
    }

    for(int h = 0; h < N; h++){
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int w = 0; w < N; w++){
            altitute[h][w] = Integer.parseInt(st.nextToken());
            alts.add(altitute[h][w]);
        }
    }

    System.out.println(find(alts));
}

static int find(HashSet<Integer> alts){
    int result = 1000000;

    Integer[] alt = alts.toArray(new Integer[0]);
    Arrays.sort(alt);
    int low = 0, high = 0;
    int right = 0, left = 0;
    while(left <= right && right < alt.length){
        low = alt[left]; high = alt[right];
        vis = new boolean[N][N];
        int visitedHomes = dfs(low, high, ph, pw);
        if(visitedHomes == K){
            result = Math.min(result, high - low);
            left++;
        }else right++;
    }
    return result;
}

static int N, K = 0;
static int ph = 0, pw = 0;

static char[][] board;
static int[][] altitute;
static int[] alt;
static boolean[][] vis;
static int[][] dir = {
    {0, 1},
    {1, 1},
    {1, 0},
    {1, -1},
    {0, -1},
    {-1, -1},
    {-1, 0},
    {-1, 1}
};
//정해진 low, high로 전체 집을 탐색할 수 있는가?
static int dfs(int low, int high, int h, int w){
    if(high < low || h < 0 || h >= N || w < 0 || w >= N || vis[h][w] || low > altitute[h][w] || high < altitute[h][w]) return 0;

    vis[h][w] = true;

    int result = 0;
    if(board[h][w] == 'K') result++;
    for(int d = 0; d < dir.length; d++)   result += dfs(low, high, h + dir[d][0], w + dir[d][1]);

    return result;
}

}

```