[모의 SW 역량테스트 - 1949] 등산로 조성

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq&categoryId=AV5PoOKKAPIDFAUq&categoryType=CODE

SW Expert Academy

 

로그인을 한 뒤 위 링크로 들어가면 문제를 볼 수 있습니다.

 

처음에 문제를 잘못 읽어 헤맸던 문제

 

'문제를 빠르게 읽고 가장 긴 등산로만 구하면 되겠구나!' 해서 문제를 풀었다 이상한 값이 나오고 당황했었다.

 

하지만 문제를 다시 읽고 접근해보니 2가지 포인트를 놓치고 있었다.

 

1. 등산로를 가장 높은곳에서 시작한다.

 

2. 딱 한 곳을 정해서 최대 k 깊이 만큼 지형을 깎을 수 있다.

(1 ~ k만큼 깎는다는 소리이다...)

 

2번 같은 경우는 나처럼 빨리 읽고 넘어가는 유형의 사람이라면 충분히.. 놓치고 갈 수 있는 부분이었다..

 

그래서 디버깅하는데 시간을 엄청 많이 써버렸다..

 

문제 난이도는 대략 A형 정도? 인 것 같다.

 

- 풀이 방법

1. 입력을 받는다.

 

2. 가장 높은 봉우리를 찾아서 큐에 넣어준다.

 

3. 큐에 들어간 값을 기준으로 dfs 탐색을 해서 가장 긴 등산로를 찾는다.

 

4. 딱 한 곳을 정해 공사하는 것은 flag 변수를 하나 만들어서 해줬다.

(여기서 포인트는 공사를 하다보면 값이 겹쳐서 그냥 넘어가는 경우가 있는데 이를 방지하기 위해 temp2, flag2라는 변수를 하나 만들어줘서 매개변수로 받아온 값을 저장시켰고 상, 하, 좌, 우 각각 탐색이 끝날때마다 이 값들로 초기화해줬다.)

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct TOP {
	int y, x;
};
int t, n, k, res;
int map[9][9];
int visited[9][9];
int top;
queue<TOP> q;
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };

void dfs(int y, int x, int len, bool flag, int temp) {
		res = max(res, len);
		int temp2 = temp;
		bool flag2 = flag;

	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny < 0 || ny >= n || nx < 0 || nx >= n || visited[ny][nx]) continue;

		if (temp == -1) {
			if (map[ny][nx] < map[y][x]) {
				visited[ny][nx] = 1;
				dfs(ny, nx, len + 1, flag, temp);
				visited[ny][nx] = 0;
			}
			else {
				if (flag) {
					for (int i = 1; i <= k; i++) {
						if (map[ny][nx] - i >= 0 && map[ny][nx] - i < map[y][x]) {
							temp = map[ny][nx] - i;
							flag = false;
							visited[ny][nx] = 1;
							dfs(ny, nx, len + 1, flag, temp);
							visited[ny][nx] = 0;
						}
					}
				}
			}
		}
		else {
			if (temp > map[ny][nx]) {
				temp = map[ny][nx];
				visited[ny][nx] = 1;
				dfs(ny, nx, len + 1, flag, temp);
				visited[ny][nx] = 0;
			}
		}
		temp = temp2;
		flag = flag2;
	}
}

int main(void) {

	scanf("%d", &t);

	for (int tc = 1; tc <= t; tc++) {
		res = 0;
		top = 0;

		scanf("%d %d", &n, &k);

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				scanf("%d", &map[y][x]);
			}
		}

		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				top = max(top, map[y][x]);
			}
		}
		
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < n; x++) {
				if (top == map[y][x]) {
					q.push({ y,x });
				}
			}
		}

		while (!q.empty()) {
			int y = q.front().y;
			int x = q.front().x;
			q.pop();

			visited[y][x] = 1;
			dfs(y, x, 1, true, -1);
			visited[y][x] = 0;
		}
		printf("#%d %d\n", tc, res);
	}

	getchar();
	getchar();

	return 0;
}