2842 - 집배원 한상덕 (더블 포인터, DFS)

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

2842번: 집배원 한상덕

이 문제 진심 개 같아요.

 

그냥 개 같아요.

개빡침

문제가 개 같다는건, 극찬입니다. 비슷한 예로 '게임 ㅈ같이 하네' 라는 문구도 상대방에게 극찬을 하는 의미이죠.

 

처음에 이 문제를 접했을 때, 이분탐색으로 접근했습니다. 고도의 범위는 1,000,000까지이며, 이 사이에 정답이 있으니 이분탐색이면, 금방하겠다.라는 안일한 생각으로 문제를 풀었다가, 정확히, 8시간동안 고생했습니다.

이분탐색으로 조지다가 조져진건 나였다.

왤까요?

 

저에게 가장 피하기 어려운 예시가 있는데, 아래와 같습니다. 나를 진심 고생시킨 예제 개 열받네

4
.K.K
K..K
P..K
K...
88 41 83 39
53 92 15 29
34 35 7 57
34 22 80 96

여기서 정답으로 도출되야 하는 답 최저, 최고점은 15 57입니다. 즉, 42라는 말인데, 제가 Low 값은 낮고, High는 높게 동적으로 값을 변화시키다보니까 7, 57을 최저, 최고점으로 꼽게 되면서 계속 틀렸던 것이었습니다.

 

또, 시간 초과도 뜨기도 했는데, DFS를 순회할 때, 하나의 경로가 아니면 다른 경로를 찾으려고 visited를 그 때 그 때마다 초기화를 해주었습니다. (예를 들어서 A, B의 분기점이 존재하는데, A로 가다가 길이 막혀서 A에서 다시 분기점으로 되돌아와서 B로 가는 짓을 했었습니다)

 

아래가 제 틀렸던 코드입니다.

#include <stdio.h>

int N, arr[50][50];
char str[50][50];
int visited[50][50] = { 0, };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };

int sY, sX;
int kmap[2500][2] = { 0, }, kcnt = 0;

int Gmin = 0xffffff, Gmax = 0;

int H, L, hiK, mid;

int result = 0;

void input() {
	scanf("%d", &N);
	for (int n = 0; n < N; ++n) {
		scanf("%s", str[n]);
	}
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) scanf("%d", &arr[i][j]);
	}
}

void fsp() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (str[i][j] == 'P') {
				sY = i;
				sX = j;
			}
		}
	}
}

void fsk() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (str[i][j] == 'K') {
				kmap[kcnt][0] = i;
				kmap[kcnt][1] = j;
				++kcnt;
			}
		}
	}
}

void fmm() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (arr[i][j] < Gmin) Gmin = arr[i][j];
			if (arr[i][j] > Gmax) Gmax = arr[i][j];
		}
	}
}

void dfs(int cY, int cX) {
	for (int i = 0; i < 8; ++i) {
		int y = cY + dy[i];
		int x = cX + dx[i];
		if (0 <= y && y < N && 0 <= x && x < N && visited[y][x] == 0) {
			if (arr[y][x] - L <= mid && H - arr[y][x] <= mid) {
				if (arr[y][x] <= L) L = arr[y][x];
				if (arr[y][x] >= H) H = arr[y][x];
				visited[y][x] = 1;
				dfs(y, x);
                // visited[y][x] = 0; 이렇게 병신짓 했습니다.
			}
		}
	}
}

void bS(int min, int max) {
	if (min <= max) {
		mid = (max + min) / 2;
		H = arr[sY][sX]; L = arr[sY][sX];
		hiK = 0;

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

		visited[sY][sX] = 1;
		dfs(sY, sX);

		int tf = 1;
		for (int k = 0; k < kcnt; ++k) {
			if (visited[kmap[k][0]][kmap[k][1]] != 1) {
				tf = 0;
			}
		}
		if (tf) {
			hiK = 1;
		}

		if (hiK) {
			result = mid;
			bS(min, mid - 1);
		}
		else {
			bS(mid + 1, max);
		}
	}
}

int main(void) {
	input();
	fsp();
	fsk();
	fmm();
	bS(0, Gmax - Gmin);

	printf("%d", result);
}

젠장

 

그래서 너무 힘들어서, 풀이를 찾아보니까 더블 포인터 개념을 사용했더라고요 ??

 

개념은 저와 비슷했습니다. 정답을 정해놓고 그 정답이 되는지 안되는지 파악하는 건데, 저는 최고, 최저점의 차이를 기준으로 이분탐색을 했다면, 그 분들은 최고, 최저점의 기준을 따로 두어서 정답 가능성이 있으면, 이 두 개의 차이를 구해서 정답을 구했습니다. 즉, 정해진 최고 최저점이 있으니, 저처럼 이상하게 동적으로 최고, 최저가 변경될 여지가 없던 것이었습니다.

 

이를 이용해서 문제를 풀었고, 중요한 개념을 더 짚고 넘어가보자면

 

1. 정답이 되는지 안되는지 하기 전에 visited를 계속해서 초기화를 시켜줘야한다.

2. 정답이 되는지에 대한 기준은 이동할 고도가 정답 후보의 최저와 정답 후보의 최고 사이에 있어야하는 값이어야 한다. (이 개념이 가장 이해하기 힘들었습니다)

3. 2번 개념의 연장으로 P 지점 역시 정답 후보의 최저와 정답 후보의 최고 사이에 있어야하는 값이어야 한다. (이거 못해서 한 번 틀렸습니다)

4. 정답은 어차피 주어진 숫자 배열 안에 있기 때문에 이를 중복 없이 오름차순으로 만들어서 정답을 구해야한다.

5. 정답 가능성이 없다면 right(최고 지점)을 올려주고, 정답 가능성이 있다면 left(최저 지점)을 올리고 전역 정답 후보와 현재 정답 후보의 값을 비교해서 갱신을 해줍니다.

 

여기까지 잘 수행하셨다면, 다들 충분히 푸실 수 있으실 겁니다. 저는 멍청해서 오래걸렸네요.

#include <stdio.h>

int N;
char str[51][51];
int arr[51][51];

int k_map[2500][2], k_cnt = 0;
int p[2];

int height[2500] = { 0, }, height_cnt = 0, temp_height[1000001] = { 0, };

int dy[8] = { -1, 0, 1, 1, 1, 0, -1 ,-1 };
int dx[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int cy, cx;

int left = 0, right = 0, visited[50][50];

int result = 0xffffff;

void input() {
	scanf("%d", &N);
	for (int n = 0; n < N; ++n) scanf("%s", str[n]);
	for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) scanf("%d", &arr[i][j]);
}

void make_k_map() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (str[i][j] == 'K') {
				k_map[k_cnt][0] = i;
				k_map[k_cnt][1] = j;
				k_cnt++;
			}
		}
	}
}

void find_p() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			if (str[i][j] == 'P') {
				p[0] = i;
				p[1] = j;
			}
		}
	}
}

void set_height() {
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			temp_height[arr[i][j]] = 1;
		}
	}
	for (int i = 0; i < 1000000; ++i) {
		if (temp_height[i]) {
			height[height_cnt] = i;
			++height_cnt;
		}
	}
}

void dfs(int py, int px) {
	if (!visited[py][px]) visited[py][px] = 1;
	for (int i = 0; i < 8; ++i) {
		cy = py + dy[i];
		cx = px + dx[i];
		if (0 <= cy && cy < N && 0 <= cx && cx < N && !visited[cy][cx]) {
			if (height[left] <= arr[cy][cx] && arr[cy][cx] <= height[right]) dfs(cy, cx);
		}
	}
}

int v_check() {
	for (int i = 0; i < k_cnt; ++i) {
		if (!visited[k_map[i][0]][k_map[i][1]]) return 0;
	}
	return 1;
}

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

void sol() {
	while (left <= right) {
		if (right == height_cnt) break;
		init_visited();
		if (height[left] <= arr[p[0]][p[1]] && arr[p[0]][p[1]] <= height[right]) {
			dfs(p[0], p[1]);
		}
		if (v_check()) {
			if (height[right] - height[left] < result) result = height[right] - height[left];
			++left;
		}
		else ++right;
	}
}

int main(void) {
	input();
	make_k_map();
	find_p();
	set_height();
	sol();
	printf("%d", result);
}

알고리즘 너무 쉬니까, 머리가 안 돌아가네요.

 

이래가지고 Pro 딸 수 있을까 모르겠습니다.

---

이상 2842 - 집배원 한상덕 (더블 포인터, DFS)였습니다. ^_^