[백준 2842] 집배원 한상덕

문제 링크 : 2842번: 집배원 한상덕 (acmicpc.net)

2842번: 집배원 한상덕

문제

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

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

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

입력

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

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

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

출력

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

---

투 포인터를 곁들인 BFS 문제이다.

 

우체국('P')를 시작으로 하여 모든 집('K')까지 이동하면서 만들어지는 피로도(높은 고도 - 낮은 고도)의 Minimum 값을 구하는 것이 문제이다.

투 포인터를 이용하여 가장 낮은 고도로부터 시작하여 가장 높은 고도까지 left, right 값을 조정해가면서 모든 집('K')에 이동 가능한지를 판별한다.

그리고 모든 집에 이동한 경우 피로도(높은 고도 - 낮은 고도) 값을 갱신하면서 가장 적은 피로도 값을 구할 수 있다.

 

※ 문제 접근 방법

① 마을 N x N 의 모든 고도들을 벡터 v에 저장한 후에 오름차순으로 정렬한다.

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

 

② 투 포인터 기법을 이용하기 위해서 (l, r) 값을 초기에 0으로 선정한다. (가장 낮은 고도(v[0])부터 시작)

bfs를 이용하여 [v[l], v[r]] 범위 내에 우체국('P')을 시작으로 하여 모든 집('K')까지 이동 가능한지 확인한다.

• [v[l], v[r]] 범위 내에 모든 집을 이동 가능한 경우 : l 값을 1 증가시키고 피로도의 최소값을 업데이트 해준다.
• [v[l], v[r]] 범위 내에 모든 집을 이동 불가능한 경우 : r 값을 1 증가시킨다. 

int l = 0, r = 0, fatigue = INF;
while (l < v.size() && r < v.size()) {
	init();
	if (bfs(curX, curY, l, r)) {
		fatigue = min(fatigue, v[r] - v[l]);
		l += 1;
	}
	else {
		r += 1;
	}
}

 

③ ② 에서 투 포인터가 종료되면 피로도 값을 반환한다.

 

Solution Code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

int N, curX, curY, size_K;
int dx[8] = { -1,-1,-1,0,1,1,1,0 };
int dy[8] = { -1,0,1,1,1,0,-1,-1 };
int height[51][51];
char Map[51][51];
bool visited[51][51];
vector<int> v;

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		string S;
		cin >> S;
		for (int j = 0; j < N; j++) {
			Map[i][j] = S[j];
			if (Map[i][j] == 'P')
				curX = i, curY = j;
			else if (Map[i][j] == 'K')
				size_K++;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> height[i][j];
			v.push_back(height[i][j]);
		}
	}
}

bool bfs(int startX, int startY, int l, int r) {
	queue<pair<int, int>> Q;
	int cnt = 0;

	if (v[l] <= height[startX][startY] && height[startX][startY] <= v[r]) {
		Q.push({ startX,startY });
		visited[startX][startY] = true;
	}
	while (!Q.empty()) {
		int x = Q.front().first, y = Q.front().second;
		Q.pop();

		for (int i = 0; i < 8; i++) {
			int nextX = x + dx[i], nextY = y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && !visited[nextX][nextY]) {
				if (v[l] <= height[nextX][nextY] && height[nextX][nextY] <= v[r]) {
					if (Map[nextX][nextY] == 'K') 
						cnt++;
					Q.push({ nextX,nextY });
					visited[nextX][nextY] = true;
				}
			}
		}
	}

	return cnt == size_K;
}

void init() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visited[i][j] = false;
		}
	}
}

void solution() {
	int l = 0, r = 0, fatigue = INF;

	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	while (l < v.size() && r < v.size()) {
		init();
		if (bfs(curX, curY, l, r)) {
			fatigue = min(fatigue, v[r] - v[l]);
			l += 1;
		}
		else {
			r += 1;
		}
	}
	cout << fatigue;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solution();
	
	return 0;
}