백준, BOJ, 2842번, 집배원 한상덕 : C++ [CPP]

사실 어렵다기보다는

생각이 어렵다.

구현은 어렵지 않다.

솔직히 힌트를 얻어서 했지만.. 과연 내가 혼자서 할 수 있을까?? 는 고민이다.

 

 

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

 

---

 

#맞은 풀이

#include <iostream>
#include <set>
#include <iterator> //distance를 쓰기 위함
#include <algorithm>

using namespace std;
const int MAX = 51;
const int INF = 987654321;

char pos[MAX][MAX];
int height[MAX][MAX];
int visited[MAX][MAX];

int dr[8] = { -1,-1,-1,0,0,1,1,1 };
int dc[8] = { -1,0,1,-1,1,-1,0,1 };
set<int> h;

int N;
int K; //총 집 개수
int k; //DFS 탐색 시 배달한 집 개수

int sr, sc; //우체국 위치



//현재위치(r,c) , 고도 최소, 최대
void DFS(int cr, int cc, int mn, int mx) {
    visited[cr][cc] = 1;
    if (pos[cr][cc] == 'K')k++; //집에 방문했으면 k++

    for (int dir = 0; dir < 8; dir++) {
        int nr = cr + dr[dir];
        int nc = cc + dc[dir];

        if (nr<1 || nr >N || nc < 1 || nc >N)continue;//범위
        if (visited[nr][nc] == 1)continue; //방문한 곳은 다시 방문하지 않음.
        if (height[nr][nc] < mn || height[nr][nc] > mx)continue; //고도 제한
        DFS(nr, nc, mn, mx);
    }
    //방문처리를 되돌리지 않음(백트래킹 x)
}



int main() {
    cin >> N;

    //위치
    K = 0; //배달해야하는 총 집 개수
    for (int i = 1; i <= N; i++) {
        string s;
        cin >> s;
        for (int j = 1; j <= N; j++) {
            pos[i][j] = s[j-1];
            //시작위치
            if (s[j-1] == 'P') {
                sr = i;
                sc = j;
            }
            if (s[j-1] == 'K') {
                K++;
            }
        }
    }


    //고도
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> height[i][j];
            h.insert(height[i][j]); //set에 고도를 넣음(중복 x)
        }
    }

    //실행
    int ans = INF; //피로도 초기값
    //최소의 피로도를 갖게해야한다.
    //입력받은 고도를 sort한 후 -> set 이용해서 sort와 중복제거를 한 번에
    //최저 고도와 최고 고도를 제한하며 탐색을 진행한다.
    //-> 이 생각을 어떻게 하느냐??
    //고도를 고려하는 탐색은 내가 할 줄 모름 -> 그럼 고도를 제한해서 탐색하자.

    //투 포인터 초기화.
    auto it1 = h.begin();
    auto it2 = h.begin();

    while (true) {
        int mini = *it1;
        int maxi = *it2;
        //만약 현재 최고고도가 우체국보다 낮으면 돌아가지 않음. *******필수 조건 1
        if (maxi < height[sr][sc]) {
            it2++;
            continue;
        }

        //visited 초기화
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                visited[i][j] = 0;
            }
        }
        //배달한 집 개수 초기화
        k = 0;


        DFS(sr, sc, mini, maxi);
        //DFS탐색을 끝마쳤을 때
        //모든 집에 배달을 하지 못했다면 -> 최고 고도를 높여야함.
        if (K != k) {
            it2++;
            if (it2 == h.end())break;
        }
        //배달을 했다면 -> 최소 고도를 높여서 피로도를 줄일 수 있는지 확인
        else {
            //고도차이 기록
            int temp = *it2 - *it1;
            ans = min(ans, temp);

            it1++;
            //만약 우체국보다 고도가 높아지면 돌 수 없음. ********필수조건 2
            if (*it1 > height[sr][sc])break;

            //만약 고도가 다 똑같다면 it1이 역전함.
            if (it1 == h.end())break;
        }
    }


    cout << ans;

    return 0;
}

 

 

나는 이렇게 생각했다.

최저 고도, 최고 고도를 고려하면서 탐색하는 것은 힘드니까

최저 고도, 최고 고도를 제한시키자.. 그리고 범위를 좁혀나가자라고 생각했다.

이것도 힌트를 얻어서 한 것이다.

 

또한 모든 곳을 방문했는지 여부는 따로 int k 변수를 만들어서 모든 집을 방문했는지를 체크했다.

다른 방법으로는 미리 K의 좌표를 알아놓는다면 바로 해당 좌표를 방문할 때 체크해도 될 것이다.

 

아무튼 일반적으로 이분탐색으로 푼다는데.. 이분탐색이 더 감이 안온다.

투포인터로 최저 최대를 순서대로 조작하면서 해나간다.

 

고도는 set으로 정렬해놓아야한다!. 그렇지 않으면 투포인터의 의미가 사라진다.

(이 문제에 한해서)