SWEA 1949번 [모의 SW 역량테스트] 등산로 조성 C++ DFS, 완전탐색, 시뮬레이션, 구현

리뷰

SWEA 문제는 대체적으로 어려운 것 같다..

 

문제 풀이

1. tc를 입력 받고 테스트 케이스 수 만큼 for문을 개행해 준다.
2. init, input, solution 함수를 순차적으로 실행해준 후 ans에 저장된 답을 출력해 준다.

1. init()

1. cnt, ans, max_val을 0으로 초기화 해준다.

2. input()

1. n과 k값을 입력 받고 n * n 맵을 만들어 준다, 동시에 가장 높은 값을 max_val로 설정해 준다.

3. solution()

1. n * n 맵을 순회하며 가장 높은 봉우리를 찾은 경우 해당 위치를 기반으로 dfs를 시작해 준다.
2. dfs를 시작하기 전에 cnt를 1로, 방문 배열 초기화, 현재 위치를 방문처리를 해준 상태로 시작한다.

4. dfs(int x, int y, int f)

1. 매개변수로 입력받은 x, y는 해당 봉우리의 좌표이며, f는 현재보다 높은 봉우리를 만났을때 봉우리를 깎았는지 여부이다.
2. 우선 현재 cnt가 ans보다 높은 경우 ans의 값을 최신화 해준다.
3. 4방향 탐색을 하여 다음 방향이 범위를 벗어나지 않고, 방문하지 않았을 경우 이동을 진행할 수 있다.
4. 다음 좌표가 현재 봉우리 보다 낮을 경우 방문처리, cnt를 증가시키고 재귀를 시작한다, 재귀가 끝난 뒤엔 방문처리를 해제해 주고, 증가 시켰던 cnt도 원상복구 시켜주어야 한다.
5. 만약 다음 좌표가 현재 봉우리보다 높다면, 해당 봉우리를 깎을 수 있는지 여부를 판단한다.
6. f가 1인 경우 이미 봉우리를 깎은 상태이므로 고려하지 않는다.
7. f가 0인 경우 1부터 k까지를 돌려주어 이동할 수 있을 정도로 깎였을 경우 맵에서 해당 봉우리를 깎아준다.
8. 방문처리 및 cnt를 증가시킨 후 dfs를 진행하되, f는 1인 상태로 재귀를 돌아준다.
9. dfs를 빠져나온 후에는 봉우리와 방문처리, cnt증가분을 원상복구 시켜준다.

참고 사항

dfs를 들어가기 전에 현재 봉우리도 등산로에 포함된다는 점을 잊으면 안된다. (정답이 0인 경우는 없다.)

 

정답 코드

#include<iostream>
#include<cstring>

using namespace std;

int tc, n, k, ans, max_val;
int lst[8][8];
int v[8][8];
int dx[] = { 0, 0, 1, -1 };
int dy[] = { 1, -1, 0, 0 };
int cnt;

struct Pos {
	int x, y, f;
};

void init() {
	cnt = 0;
	ans = 0;
	max_val = 0;
}

void input() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> lst[i][j];
			max_val = max(max_val, lst[i][j]);
		}
	}
}

void dfs(int x, int y, int f) {
	if (ans < cnt) ans = cnt;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (0 <= nx && nx < n && 0 <= ny && ny < n && !v[nx][ny]) {
			if (lst[nx][ny] < lst[x][y]) {
				v[nx][ny] = 1;
				cnt++;
				dfs(nx, ny, f);
				cnt--;
				v[nx][ny] = 0;
			}
			else {
				if (!f) {
					for (int j = 1; j <= k; j++) {
						if (lst[nx][ny] - j < lst[x][y]) {
							v[nx][ny] = 1;
							lst[nx][ny] -= j;
							cnt++;
							dfs(nx, ny, f + 1);
							lst[nx][ny] += j;
							cnt--;
							v[nx][ny] = 0;
						}
					}
				}
			}
		}
	}
}

void solution() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (lst[i][j] == max_val) {
				cnt = 1;
				memset(v, 0, sizeof(v));
				v[i][j] = 1;
				dfs(i, j, 0);
			}
		}
	}
}

int main() {
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		init();
		input();
		solution();
		cout << "#" << t << " " << ans << "\n";
	}
}