1949. [모의 SW 역량테스트] 등산로 조성

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PoOKKAPIDFAUq#;return%20false;

SW Expert Academy

 

DFS문제. 봉우리에서 출발하면서 각 방향 이동 시 작은 경우 그냥 이동 큰 경우 1~K까지 깎을 수 있는지 판단하면서 이동. 깎았다면 다음 좌표에서는 못 깎도록 flag 설정.

그리고 visit가 필요 없을 거라고 생각했으나, 이미 왔던 경로를 깎아서 다시 올라가는 경우가 생기므로 visit처리 해야 함.

 

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

using namespace std;


int arr[8][8];
bool visit[8][8];
int N,K;
int bongy, bongx;
int cur, result;

bool flag;

void DFS(int y, int x)
{
	
	bool check = false;

	if (y - 1 >= 0 && !visit[y-1][x])
	{
		if (arr[y - 1][x] < arr[y][x])
		{
			check = true;
			cur++;
			visit[y - 1][x] = true;
			DFS(y - 1, x);
			visit[y - 1][x] = false;
			cur--;
		}
		else
		{
			if (!flag)
			{
				for (int k = 1; k <= K; k++)
				{
					if (arr[y - 1][x] - k < arr[y][x])
					{
						check = true;
						arr[y - 1][x] -= k;
						cur++;
						flag = true;
						visit[y - 1][x] = true;
						DFS(y - 1, x);
						visit[y - 1][x] = false;
						flag = false;
						cur--;
						arr[y - 1][x] += k;
					}
				}
				
			}
		}
	}

	if (y + 1 < N && !visit[y + 1][x])
	{
		if (arr[y + 1][x] < arr[y][x])
		{
			check = true;
			cur++;
			visit[y + 1][x] = true;
			DFS(y + 1, x);
			visit[y + 1][x] = false;
			cur--;
		}
		else
		{
			if (!flag)
			{
				for (int k = 1; k <= K; k++)
				{
					if (arr[y + 1][x] - k < arr[y][x])
					{
						check = true;
						arr[y + 1][x] -= k;
						cur++;
						flag = true;
						visit[y + 1][x] = true;
						DFS(y + 1, x);
						visit[y + 1][x] = false;
						flag = false;
						cur--;
						arr[y + 1][x] += k;
					}
				}
			}
		}
	}
	
	if (x - 1 >= 0 && !visit[y][x - 1])
	{
		if (arr[y][x-1] < arr[y][x] )
		{
			check = true;
			cur++;
			visit[y][x - 1] = true;
			DFS(y , x-1);
			visit[y][x - 1] = false;
			cur--;
		}
		else
		{
			if (!flag)
			{
				for (int k = 1; k <= K; k++)
				{
					if (arr[y][x-1] - k < arr[y][x])
					{
						check = true;
						arr[y][x-1] -= k;
						cur++;
						flag = true;
						visit[y][x - 1] = true;
						DFS(y, x - 1);
						visit[y][x - 1] = false;
						flag = false;
						cur--;
						arr[y][x-1] += k;
					}
				}
			}
		}
	}

	if (x + 1 < N && !visit[y][x+1])
	{
		if (arr[y][x + 1] < arr[y][x])
		{
			check = true;
			cur++;
			visit[y][x + 1] = true;
			DFS(y, x + 1);
			visit[y][x + 1] = false;
			cur--;
		}
		else
		{
			if (!flag)
			{
				for (int k = 1; k <= K; k++)
				{
					if (arr[y][x + 1] - k < arr[y][x])
					{
						check = true;
						arr[y][x + 1] -= k;
						cur++;
						flag = true;
						visit[y][x + 1] = true;
						DFS(y, x + 1);
						visit[y][x + 1] = false;
						flag = false;
						cur--;
						arr[y][x + 1] += k;
					}
				}
			}
		}
	}
	
	if (!check)
	{
		if (result < cur)
		{
			result = cur;
		}
		return;
	}
}

int main(void)
{
	int tc;
	cin >> tc;

	for (int t = 1; t <= tc; t++)
	{
		cin >> N >> K;
		flag = false;
		cur = 1;
		result = 0;
		memset(visit, 0, sizeof(visit));

		int maxa = 0;

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				cin >> arr[i][j];
				if (maxa < arr[i][j])
				{
					maxa = arr[i][j];
				}
			}
			
		}

		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (arr[i][j] == maxa)
				{
					bongy = i;
					bongx = j;
					visit[i][j] = true;
					DFS(i, j);
					visit[i][j] = false;
				}
			}
		}

		cout << "#" << t << " " << result << endl;

	}




}