BOJ 2842번 : 집배원 한상덕

문제

문제 바로가기> BOJ 2842번 : 집배원 한상덕

2842번: 집배원 한상덕

 

풀이

고도를 ±1 씩 모든 경우의 수를 구할 경우 시간 초과가 발생한다. 50*50*1,000,000 = 2,500,000,000 (25억,,)

하지만 실제 고도의 개수는 50*50 = 2500을 초과할 수 없고, 이를 반영해서 "투 포인터 + 그래프 탐색"으로 풀었다.

 

1. 투포인터를 이용하기 위해 고도를 정렬해야 한다.

   이때, 중복되는 값은 필요 없으므로!! set을 이용해서 중복되는 값을 제거해주었다.

 

2. 투포인터를 이용해서 (low ~ high) 고도 내에서 모든 집에배달이 가능한지 확인한다.

    배달이 불가한 경우, high를 올려준다! (엇? 넘을 수없는 문턱이 있어,,! 배달 불가야!)

    배달이 가능한 경우, low를 올려준다! (어라? 피로도 더 줄일 수 있을 거 같은데? 라는 마인드로!)

 

    ++ 우체국에서 출발하므로, 우체국의 고도는 반드시 포함되어야 한다!

    

 

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<set>
#define MAX 51
#define INF 1000001
using namespace std;

int N;
int py, px;
int home_cnt=0;
set<int> setAltitude;
vector<int> vecAltitude;

char town[MAX][MAX];
bool visited[MAX][MAX];
int altitude[MAX][MAX];
int dy[] = {0, -1, -1, -1, 0, 1, 1, 1};
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};

void input(){
	cin >> N;

	string line;
	for(int i=0; i<N; i++){
		cin >> line;
		for(int j=0; j<N; j++) {
			town[i][j] = line[j];
			if(town[i][j] == 'P') {py=i; px=j;}
			else if(town[i][j] == 'K') home_cnt++;
		}
	}
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			cin >> altitude[i][j];
			setAltitude.insert(altitude[i][j]);
		}
	}

	for(auto iter : setAltitude) vecAltitude.push_back(iter);
	sort(vecAltitude.begin(), vecAltitude.end());
}

int dfs(int y, int x, int low, int high){
	visited[y][x] = true;
	int cnt = 0;
	for(int d=0; d<8; d++){
		int ny = y+dy[d];
		int nx = x+dx[d];
		if(ny<0 || ny>=N || nx<0 || nx>=N || visited[ny][nx]) continue; // 범위를 벗어난 경우, 이미 방문한 경우
		if(altitude[ny][nx]<low || altitude[ny][nx]>high) continue; // 범위 내 고도에서 방문 불가한 경우
		if(town[ny][nx] == 'K') cnt++;
		cnt+=dfs(ny, nx, low, high);
	}
	return cnt;
}

void solution(){ // 가장 작은 피로도
	int l=0, r=0, ans=INF;
	while (r < vecAltitude.size()) {
		int low = vecAltitude[l], high=vecAltitude[r];
		if(altitude[py][px]<low || altitude[py][px]>high) { r++; continue;} // 우체국 고도를 포함하지 않는 경우 (우체국에서 출발)
		memset(visited, false, sizeof(visited));
		if(dfs(py, px, low, high)==home_cnt){
			ans = min(ans, high-low);
			l++;
		}
		else r++;
	}
	cout << ans;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	input();
	solution();
}