[BOJ 백준] 집배원 한상덕(2842) C++

 

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

2842번: 집배원 한상덕

 

문제 설명 : 

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

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

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

 

입력 : 

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

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

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

출력 : 

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

 

예제 입력 : 

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

예제 출력 : 

5

 

 

접근법 : 

1) 어떻게 풀 것인가?

아이디어 : 고도는 1~100만이다

가능한 고도의 범위를 투포인터 / 이진탐색 형태로 찾는다면 어떨까

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 집배원 한상덕 2842 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

#define MAX (100+3)

using namespace std;

typedef pair<int, int> pii;

int N;

char map[MAX][MAX];
int piro[MAX][MAX];

pii startPoint;

int houseCnt;
vector<int> piroList;

queue<pii> que;

int dr[8] = { -1,-1,-1, 0,0, 1,1,1 };
int dc[8] = { -1, 0, 1,-1,1,-1,0,1 };


int ans;				// ans : 정답

void input();
void sortErase();
void twoPointer();
bool bfs(int low, int high);

int main() {
	// 1. 입력받는다
	//freopen("input.txt", "r", stdin);
	ans = 2000000000;
	input();

	// 2. 정렬하고 중복제거 한다.
	sortErase();
	
	// 3. 투포인터로 범위 조정하면서 BFS 수행
	twoPointer();

	// 4. 정답을 출력한다.
	printf("%d", ans);

	return 0;
}

void input() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf(" %c", &map[i][j]);

			if (map[i][j] == 'P') {
				startPoint = { i,j };
			}
			else if (map[i][j] == 'K') {
				houseCnt++;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &piro[i][j]);
			piroList.push_back(piro[i][j]);
		}
	}
}

void sortErase() {
	sort(piroList.begin(), piroList.end());
	piroList.erase(unique(piroList.begin(), piroList.end()), piroList.end());
}

void twoPointer() {
	int start, end;
	
	start = end = 0;

	int len = piroList.size();

	while (end < len && start < len) {
		int cur = piro[startPoint.first][startPoint.second];

		// 1. 출발포인트(우체국)이 피로 범위에 없으면 오른쪽포인터 늘리기
		if (cur < piroList[start] || cur > piroList[end]) {
			end++;
			continue;
		}

		// 2. 현재 범위에서 bfs 도전
		if (bfs(piroList[start], piroList[end])) {
			if (ans > piroList[end] - piroList[start]) {
				ans = piroList[end] - piroList[start];
			}
            start++;		// 더 작은 값 찾아보자
		}
		// 2-1. bfs 실패했으므로 오른쪽 포인터 늘리기
		else {
			end++;
		}

	}
}

bool bfs(int low, int high) {

	bool visit[MAX][MAX];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			visit[i][j] = false;
		}
	}

	que = queue<pii>();

	int deliverCnt = 0;

	visit[startPoint.first][startPoint.second] = true;
	que.push(startPoint);

	while (!que.empty()) {
		pii cur = que.front();
		que.pop();

		int nr, nc;
		for (int i = 0; i < 8; i++) {
			nr = cur.first + dr[i];
			nc = cur.second + dc[i];

			// 지도 범위에서 벗어나면 continue
			if (nr < 0 || nc < 0 || nr >= N || nc >= N) continue;

			// 방문했거나, 피로도의 범위에서 벗어나거나 continue
			if (visit[nr][nc] == true ||
				piro[nr][nc] < low || piro[nr][nc] > high) continue;

			// 집 배달 성공할 경우 카운트 추가
			if (map[nr][nc] == 'K') {
                deliverCnt++;
                // 집을 모두 찾았을 경우에만 true
                if (deliverCnt == houseCnt) {
            		return true;
	            }
            }

			visit[nr][nc] = true;
			que.push({ nr,nc });
		}
	}

	return false;
}

#endif