c++/알고리즘

[c++] 백준-집배원 한상덕(이분탐색 , 투포인터)

hojung 2023. 2. 8.

728x90

1. 문제

2. 입출력 및 예제

3. 문제 해설

이 문제는 난이도가 플레5였기 때문에 맞출 수 있었던 거 같다.

생각 자체는 어렵지 않았지만 이렇게까지 해야한다고...? 라는 생각이 들었다.

만약 골드하위나 실버였다면 분명 이게 아니라 다른 방법이 있을거야..라고 계속 생각만 했을 거 같았다.

이 문제의 핵심은 고도차를 최소로 모든 집을 방문해야한다는 것이다.

또한 문제를 읽어보니 N이 50으로 아주 작았다. 대부분의 경우 N이 작으면 완전탐색으로 풀어야하는 경우가 많지만 map으로 나타내면 50*50의 노드를 갖기 때문에 완전탐색의 경우의 수로 풀릴 것 같진 않았다.

따라서 생각해낸 아이디어는 이것이다.

입력받은 고도를 모두 담아 중복을 제거하고 sort한다.
우체국의 고도와 집의 고도 중 가장 큰 것을 기억한다.(어차피 우체국과 집은 무조건 들려야하기 때문이다.)
그 고도 내에서 돌려보고 만약 모든 집을 들를 수 없다면 1번의 sort된 고도에서 2번의 가장 큰 고도보다 한 칸을 높인 후 다시 가본다.
만약 모든 집을 들릴 수 있다면 가장 작은 고도를 올려 다시 가본다. 만약 갈 수 있다면 다시 한 칸 올린다.
max고도가 입력 받은 고도의 최댓값을 넘어가거나 min고도가 max고도와 같거나 커지면 반복문을 종료한다.

입력받은 고도 중복 제거 및 정렬

이 과정은 STL의 <algorithm> 헤더 파일에 들어있는 unique함수와 vector의 erase함수를 이용하면 가볍게 처리할 수 있다.

#include <algorithm>
#include <vector>
#include <iostream>
int N;
vector<int> v;
char maps[51][51];
int dist[51][51];
void input() {
	cin >> N;
    for(int i=1; i<=N; i++){
    	for(int j=1; j <=N; j++) {
        	cin >> maps[i][j];
        }
    }
    for(int i=1; i<=N; i++){
    	for(int j=1; j <=N; j++) {
        	cin >> dist[i][j];
            v.push_back(dist[i][j]); // 모든 거리 입력
        }
    }
}

다음과 같이 모든 거리를 입력받은 벡터를

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

STL의 unique함수는 중복되는 원소를 하나씩 빼서 정렬한 후 끝의 인덱스를 반환한다. 즉

11223344445를 12345123444로 정렬한 후 5다음 인덱스인 5를 반환한다는 것이다. 그래서 그 인덱스서부터 v.end()에 해당하는 이터레이터까지 삭제하면 v는 12345만 남는다. (중복되는 원소들을 모두 삭제할 수 있다. )

dfs로 map탐색

dfs를 이용해 map을 탐색한다.

제약조건은 세가지가 존재한다.

만약 map의 범위를 넘었을 때
이미 방문한 곳인 경우
설정한 고도 제한에 해당하지 않을 때

void dfs(int r, int c, int mx, int mn) {
	visited[r][c] = 1;
	if (maps[r][c] == 'K') { 
		cnt++; 
	}
	for (int i = 0; i < 8; i++) {
		int nr = r + dy[i];
		int nc = c + dx[i];
		if (nr <= 0 || nc <= 0 || nr > N || nc > N || visited[nr][nc]) continue;
		if (dist[nr][nc] > mx || dist[nr][nc] < mn) continue;
		dfs(nr, nc, mx, mn);
	}
}

따라서 위와 같이 코드를 작성할 수 있다.

dy[i], dx[i]는 상하좌우 대각선의 방향 벡터에 해당한다.

투포인터 설정

투포인터를 하나는 가장 작은 고도 하나는 가장 큰 고도로 설정한다.

가장 큰 고도의 초기 값은 입력받은 우체국과 집의 고도 중 가장 높은 고도에 해당한다.

dfs를 돌릴 때마다 방문한 집의 개수를 count해준다.

만약 모두 방문을 하지 못했다면 고도 제한 중 최대 값을 올려준다.

그리고 다시 탐색한다.

만약 모두 방문을 했다면 최소 값을 올려준다.

다시 탐색한다.

만약 탐색이 가능하다가 최소 값을 올렸을 때 탐색이 불가능하다면 이 전 최소 값과 최대 값의 차가 정답이 된다.

void sol() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	//고도 범위 
	auto mxit = v.begin();
	auto mnit = v.begin();
	while (true) {
		int mxv = *mxit;
		int mnv = *mnit;

		if (mxv < dist[starty][startx]) {
			mxit++;
			continue; // 최대 값을 시작 점까지 이동 
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				visited[i][j] = 0; // 방문 배열 초기화
			}
		}
		cnt = 0;
		dfs(starty, startx, mxv, mnv);
		//cout << "cnt:" << cnt << "\n";
		if (cnt != house) {
			mxit++;// 방문을 다하지 못했다면 최대 값iterator를 증가시켜준다.
			if (mxit == v.end()) break; 
		}
		else {
			int tmp = *mxit - *mnit;
			ans = min(ans, tmp);
			mnit++; // 최소 값을 높여본다.
			//std::cout << "mxit : " << *mxit << "mnit" << *mnit << "\n";
			//cout << "ans : " << ans << "\n";
			if (*mnit > dist[starty][startx]) break;
			if (mnit == v.end()) break;
		}

	}
	std::cout << ans << "\n";
}

4. 코드

#pragma warning (disable:4996)

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 52
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
int N;
vector <int> v;
char maps[MAX][MAX];
int dist[MAX][MAX];
bool visited[MAX][MAX]; // 방문 배열
int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,1,1,1,0,-1,-1,-1 };
int house;
int starty, startx;
int ans = INF;
void input() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> maps[i][j];
			if (maps[i][j] == 'K') house++;
			if (maps[i][j] == 'P') {
				starty = i;
				startx = j;
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> dist[i][j];
			v.push_back(dist[i][j]);
		}
	}
}
int cnt;
void dfs(int r, int c, int mx, int mn) {
	visited[r][c] = 1;
	if (maps[r][c] == 'K') { 
		cnt++; 
	}
	for (int i = 0; i < 8; i++) {
		int nr = r + dy[i];
		int nc = c + dx[i];
		if (nr <= 0 || nc <= 0 || nr > N || nc > N || visited[nr][nc]) continue;
		if (dist[nr][nc] > mx || dist[nr][nc] < mn) continue;
		dfs(nr, nc, mx, mn);
	}
}

void sol() {
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	//고도 범위 
	auto mxit = v.begin();
	auto mnit = v.begin();
	while (true) {
		int mxv = *mxit;
		int mnv = *mnit;

		if (mxv < dist[starty][startx]) {
			mxit++;
			continue; // 최대 값을 시작 점까지 이동 
		}
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				visited[i][j] = 0; // 방문 배열 초기화
			}
		}
		cnt = 0;
		dfs(starty, startx, mxv, mnv);
		//cout << "cnt:" << cnt << "\n";
		if (cnt != house) {
			mxit++;
			if (mxit == v.end()) break;
		}
		else {
			int tmp = *mxit - *mnit;
			ans = min(ans, tmp);
			mnit++; // 최소 값을 높여본다.
			//std::cout << "mxit : " << *mxit << "mnit" << *mnit << "\n";
			//cout << "ans : " << ans << "\n";
			if (*mnit > dist[starty][startx]) break;
			if (mnit == v.end()) break;
		}

	}
	std::cout << ans << "\n";
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); std::cout.tie(NULL);
	input();
	sol();

	return 0;
}