[2일차] 시간복잡도 J - 2842: 집배원 한상덕

플래티넘 Ⅴ

 

#include <iostream>
#include <set>
#include <vector>
using namespace std;
//lb, ub 최적화 부분 다시보기
//모든 정보 저장할 필요 있는지 생각해보기
//(50*50밖에 안돼서 좀 의미없긴한데.. 클 경우도 있으니)
char mapInfo[51][51];
int mapHeight[50][50];
int visited[50][50] = { 0, };
set<int> heightsSet;
vector<int> heights;
int PX, PY, N;
int baedalCnt;

void dfs(int r, int c, int low, int high) {
	//방문했거나 배열범위 벗어나면 탐색종료
	if (visited[r][c] == 1 || r < 0 || r >= N || c < 0 || c >= N) return;
	if (mapHeight[r][c] < low || mapHeight[r][c] > high) return;
	//여기서부터 탐색하는 경우임
	if (mapInfo[r][c] == 'K') baedalCnt++;
	visited[r][c] = 1;
	//상하좌우
	dfs(r - 1, c, low, high);
	dfs(r + 1, c, low, high);
	dfs(r, c - 1, low, high);
	dfs(r, c + 1, low, high);
	//대각선
	dfs(r + 1, c + 1, low, high);
	dfs(r + 1, c - 1, low, high);
	dfs(r - 1, c - 1, low, high);
	dfs(r - 1, c + 1, low, high);

	return;
}

int main() {
	int houseNum = 0;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf(" %c", &mapInfo[i][j]);
			if (mapInfo[i][j] == 'P') {
				PX = i;
				PY = j;
			}
			else if (mapInfo[i][j] == 'K') {
				houseNum++;
			}
		}
	}

	printf("map info 출력\n");
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			printf("%c ", mapInfo[i][j]);
		}
		printf("\n");
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &mapHeight[i][j]);
			heightsSet.insert(mapHeight[i][j]);
		}
	}
	
	set<int>::iterator iter;
	for (iter = heightsSet.begin(); iter != heightsSet.end(); iter++) {
		heights.push_back(*iter);
	}

	int lowIdx = 0;
	int highIdx = 0;
	int pirodo = 1000000;
	while (highIdx < heights.size() && lowIdx <= highIdx) {
		baedalCnt = 0;
		int low = heights[lowIdx];
		int high = heights[highIdx];
		dfs(PX, PY, low, high);
		//printf("범위: %d 이상 %d 이하\n", low, high);

		/*
		printf("visited 출력\n");
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				printf("%d ", visited[i][j]);
			}
			printf("\n");
		}
        */

		//dfs 돌고나서 visited 초기화
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				visited[i][j] = 0;
			}
		}
		//배달 다 돌았는지 확인
		if (baedalCnt == houseNum) {
			printf("-->!배달 다함\n");
			//집 모두 감 -> 범위 줄여보기
			lowIdx++;
			//여기서 최소값 나옴 -> 갱신
			if ((high - low) < pirodo) {
				pirodo = (high - low);
				printf("피로도 갱신: %d\n", pirodo);
			}
		}
		else {//못감 -> 범위 확장
			highIdx++;
		}
	}
	printf("%d", pirodo);
}

 

DFS(또는 BFS) + two pointer 알고리즘

 

어차피 허용하는 범위가

(map 상의 높이_1) ~ (map 상의 높이_2) 일 것이므로...

이렇게 허용했을 때 괜찮나?(배달 다 돌았나?) 를 보고...

괜찮은 녀석들 중에서 피로도가 가장 적은 쪽으로 search 하도록...

하는 그런 거.

 

구하는 것: 배달을 다 돌게 하는 경로 중에서 가장 작은 높이차

              -> (조건을 만족)하는 것 중에서 (가장 작은 높이차)

 

조건과 구하는 것(==높이 차)이 연관되어있나?

조건 : 배달을 다 돌게 하는 경로 -> 높이차와 연관되어 생각하기

-> 배달을 다 돌게 하는 높이 차

 

-------------------------------------------------

 

2022.07.05

새로 푼 코드

#include <iostream>
#include <vector>
#include <set>
using namespace std;

struct P {
	int x, y;
};

P post;
vector<P> house;

int n;
char map[51][51];
int height[50][50];
bool visit[50][50];
int didj[8][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1} };

void dfs(int i, int j, int low_limit, int high_limit) {
	for (int k = 0; k < 8; k++) {
		int ni = i + didj[k][0];
		int nj = j + didj[k][1];

		if (ni < 0 || ni >= n || nj < 0 || nj >= n) continue;
		if (visit[ni][nj]) continue;
		if (height[ni][nj] > high_limit || height[ni][nj] < low_limit) continue;
		visit[ni][nj] = true;
		dfs(ni, nj, low_limit, high_limit);
	}
}

void init_visit() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = false;
		}
	}
}

bool check_all_visit(int low_limit, int high_limit) {
	int start_h = height[post.x][post.y];
	if (start_h < low_limit || start_h > high_limit) return false;
	init_visit();
	visit[post.x][post.y] = true;
	//여기까지가 bfs 시작점에 대한 처리

	dfs(post.x, post.y, low_limit, high_limit);
	for (int k = 0; k < house.size(); k++) {
		int hi = house[k].x;
		int hj = house[k].y;
		if (!visit[hi][hj]) return false;
	}
	return true;
}

int main() {
	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') {
				post.x = i;
				post.y = j;
			}
			else if (map[i][j] == 'K') house.push_back({ i, j });
		}
	}

	set<int> s;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &height[i][j]);
			s.insert(height[i][j]);
		}
	}

	vector<int> height_set;
	set<int>::iterator iter;
	for (iter = s.begin(); iter != s.end(); iter++) {
		height_set.push_back(*iter);
	}

	int low_idx = 0;
	int high_idx = 0;
	int pirodo = 1000001;

	while (high_idx < height_set.size()) {
		int low = height_set[low_idx];
		int high = height_set[high_idx];

		//다 돌았음
		if (check_all_visit(low, high)) {
			if ((high - low) < pirodo) pirodo = (high - low);
			low_idx++;
		}
		else {
			//다 못돌았음
			high_idx++;
		}
	}
	printf("%d", pirodo);
}

 

처음에는 옛날 내 코드 보고

아니 dfs를 무조건 간 다음에 범위를 보네 하고 쯧쯧 했는데

저렇게 풀지 않아서 코너 케이스에서 틀려가지고

계속 붙들고 있었던...

 

55%에서 틀렸는데

시작점인 post.x, post.y 의 높이 height[post.x][post.y] 가

허용해주는 높이인 (low <= x <= high) 에 들어가지 않으면 시작도 못해야 되는데

이 부분을 놓쳐서 계속 틀렸다 ㅜ.ㅜ

 

아아아아아

dfs(i, j)에서 i, j에 대한 처리는 안해주고

ni, nj에 대한 처리만 해줄 거면

시작점에 대한 처리를 제대로 해 줘야지...ㅜ

 

교훈을 얻었다..

옛날 나처럼 무조건 봐주는 식으로 해도 좋고

밑에 코드처럼 해줄거면... 시작점에 대한 처리를 제대로 해주자