[SWEA 1949] 등산로 조성

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

SW Expert Academy

#include <cstdio>
#include <cstring>
#include <vector>
int T;
int N, K;
int ans;

int board[8 + 2][8 + 2];

struct _st
{
	int x, y;
};
std::vector<_st> Summit;
int max_h;

int visited[8 + 2][8 + 2];

void input()
{
	// init
	memset(board, 0, sizeof(board));
	Summit.clear();
	max_h = 0;
	ans = 0;


	scanf("%d %d", &N, &K);
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			scanf("%d", &board[r][c]);
			if (max_h < board[r][c]) {
				max_h = board[r][c];
				Summit.clear();
				Summit.push_back({ r, c });
			}
			else if (max_h == board[r][c]) Summit.push_back({ r, c });
		}
	}
}


void DFS(int x, int y, int curr, int use_k, int len)
{
	// dir
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };


	if (len > ans) ans = len;
	//printf("%d %d >>%d %d\n", x, y, curr, len);

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];

		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
		if (visited[nx][ny]) continue;
		
		if (board[nx][ny] >= curr && use_k == 0) {
			int next = board[nx][ny];
			for (int k = 1; k <= K; k++) {
				if (board[nx][ny] - k < curr) {
					next = board[nx][ny] - k;
					visited[nx][ny] = 1;
					DFS(nx, ny, next, 1, len + 1);
					visited[nx][ny] = 0;
					break;
				}
			}
		}
		else if (board[nx][ny] < curr) {
			visited[nx][ny] = 1;
			DFS(nx, ny, board[nx][ny], use_k, len + 1);
			visited[nx][ny] = 0;
		}
	}
}


void simulation()
{
	for (_st s : Summit) {
		visited[s.x][s.y] = 1;
		DFS(s.x, s.y, max_h, 0, 1);
		visited[s.x][s.y] = 0;
	}
}



int main()
{
	scanf("%d", &T);
	for (int t = 1; t <= T; t++) {
		input();
		simulation();
		printf("#%d %d\n",t, ans);
	}
	return 0;
}

예전에 남겨놓은 코멘트 .. 

왜 자꾸 벽부수기 문제에 매몰되는지 모르겠다.. 이 문제도 "최대로 긴 등산로"를 만드는건데 BFS + 삼차원 방문배열로 풀다가 테케 4가 계속 안나와서 댓글 보니까 DFS... 그제서야 아, 깊이 우선 탐색을 해야하는구나 싶었다. 

이건 문제 풀기 전에 생각을 많이 안한다는 반증인듯.. 생각좀 하자 생각

 

1. 입력받을 때 최댓값들을 Summit이라는 벡터에 저장해주었다. 완전탐색 과정을 한 번 줄이기 위함이다. 

2. 모든 정상점에서 DFS를 실행한다. 

이때, 시작 지점은 무조건 방문하므로, DFS 함수를 호출하기 전에 방문 배열에 시작 지점을 방문했음을 표시해주어야 한다. (이거 안해서 틀림)

3. DFS를 돌면서 현재 등산로 길이가 res(각 DFS 시행했을 때 가장 긴 길이)보다 길면 갱신한다. 

더 작은 언덕을 만났을 때는 파라미터로 넘어온 use_k를 그대로 사용하고(이때 false로 바꿔주면 안됨, 그 전에 이미 K번 깎은 이력이 있다면 또 깎으면 안되기 때문), 더 큰 언덕을 만나 K번 깎았을 때는 무조건 use_k 플래그를 true로 바꾸어 넘겨준다. 

DFS로 풀어야 하고, 큰 숫자칸 -> 작은 숫자 칸으로 이동하지만 K번 깎을 수 있다는 조건 때문에 이미 방문한 칸에 다시 되돌아 올 수 도 있으므로 방문배열 써야 한다.