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

2842 집배원 한상덕

문제

---

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

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

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

입력

---

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

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

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

출력

---

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

---

풀이)

1981번 배열에서의 이동문제처럼

이분탐색을 이용해서 풀어보려했으나, 범위 값 설정의 어려움으로 

계속 틀려서 결국 다른 분 풀이의 도움을 받았다.

두 개의 포인터와 bfs를 이용해서 풀 수 있다.(bfs말고 dfs를 이용해도 된다.)

과정

1. 고도 값들을 따로 저장한 다음에 그것들을 오름차순으로 정렬한 뒤, 중복된 고도 값은 없애준다.

2. 고도값을 저장한 벡터를 height[]라고 할때,

    초기 left 와 right는 0으로 두고

    상원이가 이동할 수 있는 고도 값의 범위를 height[left] ~ height[right]라고 한다.

   while(right < height.size()){

while(1){

//상원이가 height[left] ~ height[right] 범위의 고도들만 이동해서

  모든 집에 우편을 배달할 수 있는지 체크

배달할 수 있을 경우 : 

피로도를 계산(height[right] - height[left])

고도값 범위의 낮은 고도 가리키는 인덱스를 높여준다 left++;

없을 경우 :

    break;

}

고도값 범위의 높은 고도 가리키는 인덱스를 높여준다. right++;

   }

    

 

ex) 그림으로 예를 들어서 보면

3
K.P
...
K.K
3 3 4
9 5 9
8 3 7

 이니깐, 

초기 height와 left, right는 다음과 같다.

상원이가 고도 3~3일때만 이동 가능하면, 우체국에서 출발 자체가 불가능 => 결국 모든 집에 우편 배달불가능하니깐 right 이동

 상원이가 고도 3~4 일때만 이동 가능하면 우편 배달 불가능 또 right 이동

불가능 -> 또 이동 -> 또 이동고도 3 ~ 8 일때는 가능

상원이가 3~8 고도 범위를 이동 가능하다고 하면 이 때는 모든 집에 우편 배달 가능하니깐 => 피로도 계산 8 - 3 = 5

그리고 left 이동시켜서 다시 반복..

조금 설명이 부족한듯 싶지만,, 이런식으로 고도 범위를 바꿔가며

피로도의 최소값을 찾으면 된다.

주의할 점

상원이가 현재 출발해야 하는 우체국의 고도가 범위안에 있을 때만 이동을 시작할 수 있다.

코드)

#include <stdio.h>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
 
int n;
char map[50][50];
pair<int, int> sang;
int house;
int height[50][50];
bool visited[50][50];
int dy[8] = {-1,-1,0,1,1,1,0,-1};
int dx[8] = {0,1,1,1,0,-1,-1,-1};
 
bool bfs(int s, int e) {
    queue<pair<int, int>> qu;
    qu.push({ sang.first,sang.second });
    visited[sang.first][sang.second] = true;
    int temp = 0;
    
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
        if (map[y][x] == 'K') {
            temp++;
            if (temp == house) return true;
        }
        for (int i = 0; i < 8; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (nx <0 || nx>=n || ny <0 || ny>=n || visited[ny][nx])continue;
            if (height[ny][nx] < s || height[ny][nx] > e) continue;
            visited[ny][nx] = true;
            qu.push({ ny,nx });
        }
    }
    return false;
}
 
int main() {
    scanf("%d", &n);
    getchar();
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            map[i][j] = getchar();
            if (map[i][j] == 'P') {
                sang.first = i;
                sang.second = j;
            }
            else if (map[i][j] == 'K') {
                house++;
            }
        }
        getchar();
    }
 
    
    vector <int> diff_height;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &height[i][j]);
            diff_height.push_back(height[i][j]);
        }
    }
 
    sort(diff_height.begin(), diff_height.end()); //고도 값들 오름차숨
    diff_height.erase(unique(diff_height.begin(), diff_height.end()), diff_height.end());//중복값 제외
 
    int answer = 987654321;
    int left = 0, right = 0;
 
    while (right < diff_height.size())
    {
        while (true) {
            bool suc = false;
            if (diff_height[left] <= height[sang.first][sang.second] && height[sang.first][sang.second] <= diff_height[right]) {
                suc = bfs(diff_height[left], diff_height[right]);
                memset(visited, 0, sizeof(visited));
            }
            
            if (!suc) break;
            
            int diff = diff_height[right] - diff_height[left];
            if (answer > diff) answer = diff;
            left++;
        }
        right++;
    }
    printf("%d", answer);
 
 
    return 0;
}