[swea 1949] 등산로 조성

분류 

구현

요구사항

제일 높은 봉우리 k에서부터 시작하여 내림차순으로 등산로 조성하기

단, 1번은 k만큼 깍을 수 있다

 

풀이

제일 높은 봉우리 일때만 dfs로 탐색하면 된다.

k만큼 깍을 수 있다는 것은 1~k까지 깍을 수 있다는 뜻이다.

범위가 작아서 다른 방법으로도 풀 수 있다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#include<math.h>

using namespace std;
int map[10][10];
int visit[10][10];
int n, k;
int ans = 0;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
void solve(int r, int c, int now, int flag, int cnt) {
	
	if (cnt > ans) ans = cnt;

	for (int i = 0; i < 4; i++) {
		int nr = r + dr[i];
		int nc = c + dc[i];
		if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
		if (visit[nr][nc] == 0) {
			if (map[nr][nc] < now) {
				visit[nr][nc] = 1;
				solve(nr, nc, map[nr][nc], flag, cnt+1);
				visit[nr][nc] = 0;
			}
			if (map[nr][nc] >= now) {
				if (flag == 0) {
					for (int j = 1; j <= k; j++) {
						if (map[nr][nc] - j < now) {
							visit[nr][nc] = 1;
							solve(nr, nc, map[nr][nc] - j, 1, cnt + 1);
							visit[nr][nc] = 0;
						}
					}
				}
			}
		}
	}



}
int main() {
	int t;
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		ans = 0;
		memset(visit, 0, sizeof(visit));
		scanf("%d%d", &n, &k);
		int height = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				scanf("%d", &map[i][j]);
				height = max(height, map[i][j]);
			}
		}

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == height) {
					visit[i][j] = 1;
					solve(i, j, map[i][j], 0, 1);
					visit[i][j] = 0;
				}
				if (map[i][j] > height) {
					for (int ii = 1; ii <= k; ii++) {
						if (map[i][j] - ii == height) {
							visit[i][j] = 1;
							solve(i, j, map[i][j]-ii, 1, 1);
							visit[i][j] = 0;
						}
					}
				}
			}
		}
		
		printf("#%d %d\n", tc, ans);
	}
}