1949. 등산로 조성

//2차원 배열 문제 풀이 시
//항상 d[4][2], visit, out_of_bound()는 정의하고 시작할 것.
//out_of_bound -> visit -> ...

static int N, K;
static int board[8][8];
static int ans;
static bool visit[8][8];
static int d[4][2] = {
	-1, 0,
	1, 0,
	0, -1,
	0, 1
};

static bool out_of_bound(int y, int x)
{
	if (y < 0 || y >= N)
		return true;
	if (x < 0 || x >= N)
		return true;
	return false;
}

static void __solution(int y, int x, int len, int is_cut)
{
	if (len > ans)
		ans = len;

	visit[y][x] = true;
	for (int dir = 0; dir < 4; dir++)
	{
		int ny = y + d[dir][0];
		int nx = x + d[dir][1];

		if (out_of_bound(ny, nx))
			continue;
		if (visit[ny][nx])
			continue;

		int cur = board[y][x], next = board[ny][nx];
		if (next < cur) //진행 할 수 있음
			__solution(ny, nx, len + 1, is_cut);
		else //진행 할 수 없는데,
		{
			if (is_cut) //한번 공사를 했음
				continue;
			else //공사를 할 수 있음,
			{
				int needs = next - cur + 1; //자기보다 1 낮아야 더 많이 갈 수 있음.
				if (K >= needs) //충분히 깎을 수 있으면
				{
					board[ny][nx] -= needs;
					__solution(ny, nx, len + 1, 1);
					board[ny][nx] += needs;
				}
				else //깎을 수 없으면,
					continue;
			}
		}
	}
	visit[y][x] = false;
}

static int solution()
{
	int max = -1;
	vector<pair<int, int>> v;

	scanf("%d %d", &N, &K);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &board[y][x]);
			if (board[y][x] >= max)
			{
				if (board[y][x] > max)
					v.clear();
				max = board[y][x];
				v.push_back({ y, x });
			}
		}
	}

	ans = 0;
	for (int i = 0; i < v.size(); i++)
	{
		int y = v[i].first, x = v[i].second;
		__solution(y, x, 1, 0); //시작하는 순간 부터 길이는 1이되야함.
	}

	return ans;
}

dfs시작은 높이가 제일 높은 위치 부터 시작해야 하고, 코드 구조 상 그 길이는 1 부터 시작해야 한다.

이차원 배열에서 d를 이용하여 순회 할 때에는 첫번째로 항상 out_of_bound()로 범위를 벗어나는지 체크해야 한다.

그 다음은 visit을 이용하여 왔던 길을 되돌아 가는지 여부를 파악해야 한다.

 

이 두 테스트를 통과해야지만 dfs를 계속 이어 나갈 수 있는것이다.

 

예전 풀이에서 한번 정리했던 것 처럼, 공사를 할 때에는 현재 높이 보다 1만큼 작게 깎을 수 있는지 확인해야 한다.

5 -> 7 ->3 -> 2 -> 1 이렇게 가야한다고 했을 때,

7을 굳이 2로 깎을 필요는 없다. 5 - 1 = 4 로 깎아야지 뒤이어 오는 값들을 최대한 많이 활용할 수 있기 때문이다. 

 

 

//주의사항 및 정리

1. 이차원배열 관련된 문제가 나오면 필요하든, 필요하지 않든 out_of_bound(), visit[][] d[4][2]는 일단 정의하고 늘 필요한지 생각할 것.