SW Expert Academy - 1949. 등산로 조성

문제링크

• 등산로 조성

문제설명

• N x N 크기의 등산로를 만들기 위한 부지가 주어지고, 이곳에 최대한 긴 등산로를 만들어야 한다.
• 각 칸의 숫자는 지형의 높이를 나타낸다.
• 등산로는 아래와 같은 규칙으로 만들어진다.
  • 등산로는 가장 높은 봉우리에서 시작해야 한다.
  • 등산로는 산으로 올라갈 수 있도록 반드시 높은 지형에서 낮은 지형으로 가로 또는 세로 방향으로 연결이 되어야 한다.
  • 긴 등산로를 만들기 위해 딱 한 곳을 정해서 최대 K 깊이만큼 지형을 깎는 공사를 할 수 있다.
• 만들 수 있는 가장 긴 등산로를 찾아 길이를 출력하라

문제접근1

• 브루트포스 + 백트래킹 로 해결한다.
• 등산로를 만들 시작 지점은 가장 높은 봉우리에서 시작해야 하므로 시작점으로 가능한 봉우리의 좌표 정보를 배열에 담아둔다.
• 딱 한 곳의 지형을 최대 K 깊이만큼 깎아서 높이를 낮출 수 있고, 1 보다 작은 높이로도 만들 수 있으므로 모든 칸에 대해서 0~K 만큼 지형을 깎아가며 완전탐색(백트래킹)을 한다.
• 백트래킹 구조
  • 현재 이동한 칸의 높이가 이전 땅의 높이보다 높거나 같은 경우 현재까지의 거리를 반환하고 이전 탐색 지점으로 되돌아 간다.
  • 상하좌우로 이동하며 재귀 호출로 등산로를 탐색한다.

구현1

#include <iostream>
#include <memory.h>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX_N 8

using namespace std;

int board[MAX_N][MAX_N];
int N, K;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
vector<pair<int, int>> startPoints;
int visited[MAX_N][MAX_N];

int makeTrack(int xpos, int ypos, int height, int dist) {
	// 이동한 곳의 높이가 이동하기 전 높이와 같거나 더 높은 경우
	if (board[xpos][ypos] >= height && dist > 0) {
		return dist;
	}

	int ret = 0;
	for (int dir = 0; dir < 4; dir++) {
		int nx = xpos + dx[dir];
		int ny = ypos + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
		if (visited[nx][ny])continue;
		visited[nx][ny] = true;
		ret = max(ret, makeTrack(nx, ny, board[xpos][ypos], dist + 1));
		visited[nx][ny] = false;
	}
	return ret;
}

void updateStartPoints(int maxHeight) {
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (maxHeight == board[r][c])
				startPoints.push_back(make_pair(r, c));
		}
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> N >> K;
		int maxHeight = 0;
		startPoints.clear();
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				cin >> board[r][c];
				if (maxHeight < board[r][c]) maxHeight = board[r][c];
			}
		}
		updateStartPoints(maxHeight);
		int ans = 0;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				for (int i = 0; i <= K; i++) {
					board[r][c] -= i;
					for (auto ele : startPoints) {
						memset(visited, false, sizeof(visited));
						ans = max(ans, makeTrack(ele.first, ele.second, board[ele.first][ele.second], 0));
					}
					board[r][c] += i;
				}
			}
		}
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

문제접근2

• 공사를 할 수 있는 경우를 확인하며 백트래킹을 한다.

구현2

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>
#include <queue>

#define MAX_N 8
using namespace std;

int N, K;
int board[MAX_N][MAX_N];
int visited[MAX_N][MAX_N];
int highest;
vector<pair<int, int>> startPoints;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int ans = 0;

void input()
{
	memset(board, 0, sizeof(board));
	startPoints.clear();
	highest = 0;
	ans = 0;
	cin >> N >> K;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
			highest = max(highest, board[r][c]);
		}
	}

	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			if (board[r][c] == highest) startPoints.push_back(make_pair(r, c));
		}
	}
}

void backtracking(int cx, int cy, bool bcut, int clength)
{
	ans = max(ans, clength);

	for (int dir = 0; dir < 4; dir++) {
		int nx = cx + dx[dir];
		int ny = cy + dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
		if (visited[nx][ny]) continue;
		visited[nx][ny] = true;
		int nheight = board[nx][ny];
		if (nheight < board[cx][cy]) backtracking(nx, ny, bcut, clength + 1);
		else if (bcut == false && (nheight - board[cx][cy] + 1) <= K) {
			board[nx][ny] = board[cx][cy] - 1;
			backtracking(nx, ny, true, clength + 1);
			board[nx][ny] = nheight;
		}
		visited[nx][ny] = false;
	}
}

void solution()
{
	for (auto ele : startPoints) {
		memset(visited, false, sizeof(visited));
		visited[ele.first][ele.second] = true;
		backtracking(ele.first, ele.second, false, 1);
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("sample_input.txt", "r", stdin);
	cin >> T;
	
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		solution();
		cout << "#" << test_case << " " << ans << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}