[ BOJ 백준 2842번 - 집배원 한상덕 ] 해설 및 코드

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

 

 

 

목적

모든 집에 배달을 할 수 있는 피로도(=방문한 최고 고도와 최저 고도의 차이)의 최소값을 구하라.

 

 

 

 

접근법

1. 최저 고도와 최고 고도를 결정하기 위해 투 포인터 알고리즘을, 배달 가능한지 여부를 확인하기 위해 DFS로 접근하자. 우선, 투 포인터 방식을 적용하기 위해, 아래 그림과 같이 고도를 중복 없는 정렬된 형태의 배열로 가지고 있어야 한다. 구현을 쉽게 하기 위해서 set을 이용했다.

 

 

투 포인터 알고리즘 예시

 

2. 최저 고도(이하 LEFT)와 최고 고도(이하 RIGHT)를 가리키는 두 개의 포인터(코드에선 set의 iterator를 사용)를 이용해서 다음 절차를 LEFT가 배열의 끝에 도달할 때까지 반복 수행한다. (투 포인터 알고리즘 핵심...)

• RIGHT를 점근적으로 늘리면서, 배달 가능한지 여부를 확인한다.
• 만약 배달이 가능한 LEFT과 RIGHT이 정해졌다면, 이번엔 LEFT을 점근적으로 늘리면서(=구간을 좁히면서), 배달이 불가능할 때까지 반복한다.
• 위 과정을 반복함과 동시에 LEFT와 RIGHT의 차이와 피로도를 비교하여, 피로도를 갱신한다.

 

3. 배달이 가능한지 여부는 다음 과정으로 확인한다.

• DFS 알고리즘으로 이동가능한 범위 LEFT과 RIGHT을 고려하여 방문 체크를 한다.
• 위 과정을 마무리하고난 뒤, K의 개수(=집의 총 개수)만큼 반복문을 수행하여 모두 방문했는지를 검사한다.

#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
 
int n, lo,hi,a[51][51],v[51][51];
int di[]={0,0,1,-1,1,1,-1,-1},dj[]={1,-1,0,0,1,-1,1,-1};
struct pos{int i,j;};
vector<pos> K;
 
void dfs(int i,int j){
    if(i<0||j<0||i>=n||j>=n||v[i][j]||a[i][j]<lo||a[i][j]>hi)return;
    v[i][j]=1;
    for(int d=0;d<8;++d)dfs(i+di[d],j+dj[d]);
}
 
bool possible(){
    int cnt=0;
    for(int k=0;k<K.size();++k)if(v[K[k].i][K[k].j])++cnt;
    return cnt==K.size();
}
 
int main(){
    pos P;
    cin>>n;
    for(int i=0;i<n;++i){
        char t[51];cin>>t;
        for(int j=0;j<n;++j){
            if(t[j]=='P')P={i,j};
            else if(t[j]=='K')K.push_back({i,j});
        }
    }
    set<int> s;
    for(int i=0;i<n;++i)for(int j=0;j<n;++j){
        cin>>a[i][j];
        s.insert(a[i][j]);
    }
    
    int result=1e6;
    set<int>::iterator l=s.begin(),r=s.begin();
    while(r!=s.end()){
        while(l!=s.end()){
            memset(v,0,sizeof(v));
            lo=*l;hi=*r;
            dfs(P.i, P.j);
            if(!possible()) break;
            
            result=min(result,*r-*l);
            ++l;
        }
        ++r;
    }
    cout<<result;
}
 

 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.