SWEA 1949 : 등산로 조성 (모의 SW 역량테스트)

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

등산로 조성 링크

 

이후 설명 및 입/출력은 링크 참고

 

좌표를 저장하기 위한 RC 구조체를 선언한다.

MAP의 주변을 벽(-1)으로 만들고 (1, 1)부터 입력을 받는다.

입력을 받으면서 가장 높은 봉우리를 찾는다. 그리고 다시 MAP을 돌면서 가장 높은 봉우리를 start 배열에 담는다.

#define MAX (10 + 5)

int T, N, K;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC start[MAX * MAX];
int scnt;

void input()
{
	int max;

	scanf("%d %d", &N, &K);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

	max = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c]);
			if (max < MAP[r][c]) max = MAP[r][c];
		}
	}

	scnt = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == max)
			{
				start[scnt].r = r;
				start[scnt++].c = c;
			}
		}
	}
}

---

4방향 탐색을 위해 dr, dc 배열을 선언한다.

딱 한 곳을 정해서 최대 깊이 K 만큼 지형을 깎는 공사를 할 수 있다.

DFS에서 flag는 지형을 깎고 다음 DFS에 넘어왔는지 check하는 역할을 한다.

 

좌표를 기준으로 벽인 경우와 K만큼 깎아도 갈 수 없는 경우는 무시한다.

 

다음 칸이 더 작은 경우와 다음 칸을 깎아서 갈 수 있는 경우에 DFS로 다음 좌표를 저장한다.

이때, visit을 체크하고 DFS 종료 후에는 visit을 복구한다.

마찬가지로, 지형을 깎는 경우도 지형을 변경하고 DFS 종료 후에는 복구한다.

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int MAXANS;
void DFS(int L, int sr, int sc, int flag)
{
	if (MAXANS < L) MAXANS = L;

	for (int dir = 0; dir < 4; dir++)
	{
		int nr, nc;

		nr = sr + dr[dir];
		nc = sc + dc[dir];

		if (MAP[nr][nc] == -1) continue;
		if (MAP[sr][sc] <= MAP[nr][nc] - K) continue;

		/* 다음 칸이 더 작은 경우 */
		if (MAP[sr][sc] > MAP[nr][nc] && visit[nr][nc] == 0)
		{
			visit[sr][sc] = 1;
			DFS(L + 1, nr, nc, flag);
			visit[sr][sc] = 0;
		}
        
		/* 다음 칸을 깎아서 더 작은 경우 */
		else if (MAP[sr][sc] > MAP[nr][nc] - K && flag == 0 && visit[nr][nc] == 0)
		{
			int tmp = MAP[nr][nc];

			visit[sr][sc] = 1;
			flag = 1;
			/* 2칸 이상 (sr, sc)보다 작을 필요가 없다. */            
			MAP[nr][nc] = MAP[sr][sc] - 1;

			DFS(L + 1, nr, nc, flag);

			MAP[nr][nc] = tmp;
			flag = 0;
			visit[sr][sc] = 0;
		}
	}
}

 

(sr, sc)를 기준으로 (nr, nc)를 깎을 때, 가장 효율적인 방법은 MAP[sr][sc]보다 1칸만 깎을 때 뿐이다.

MAP[sr][sc]보다 2칸 이상 깎을 경우, 다음으로 갈 수 있는 등산로가 더 높아지기 때문에 의미가 없다.

즉, 최대 K칸 깎을 수 있다고 해서 1 ~ K칸 깎는 경우를 모두 해볼 필요는 없다.

 

모든 start(봉우리)에 대해 DFS를 실행하면 된다.

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (10 + 5)

int T, N, K;
int MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st
{
	int r;
	int c;
}RC;

RC start[MAX*MAX];
int scnt;

void input()
{
	int max;

	scanf("%d %d", &N, &K);

	for (int r = 0; r <= N + 1; r++)
		for (int c = 0; c <= N + 1; c++)
			MAP[r][c] = -1;

	max = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c]);
			if (max < MAP[r][c]) max = MAP[r][c];
		}
	}

	scnt = 0;
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			if (MAP[r][c] == max)
			{
				start[scnt].r = r;
				start[scnt++].c = c;
			}
		}
	}
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int MAXANS;
void DFS(int L, int sr, int sc, int flag)
{
	if (MAXANS < L) MAXANS = L;

	for (int dir = 0; dir < 4; dir++)
	{
		int nr, nc;

		nr = sr + dr[dir];
		nc = sc + dc[dir];

		if (MAP[nr][nc] == -1) continue;
		if (MAP[sr][sc] <= MAP[nr][nc] - K) continue;

		/* 다음 칸이 더 작은 경우 */
		if (MAP[sr][sc] > MAP[nr][nc] && visit[nr][nc] == 0)
		{
			visit[sr][sc] = 1;
			DFS(L + 1, nr, nc, flag);
			visit[sr][sc] = 0;
		}

		/* 다음 칸을 깎아서 더 작은 경우 */
		else if (MAP[sr][sc] > MAP[nr][nc] - K && flag == 0 && visit[nr][nc] == 0)
		{
			int tmp = MAP[nr][nc];

			visit[sr][sc] = 1;
			flag = 1;
			/* 2칸 이상 (sr, sc)보다 작을 필요가 없다. */
			MAP[nr][nc] = MAP[sr][sc] - 1;

			DFS(L + 1, nr, nc, flag);

			MAP[nr][nc] = tmp;
			flag = 0;
			visit[sr][sc] = 0;
		}
	}
}

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		MAXANS = 0;

		for (int i = 0; i < scnt; i++)
			DFS(1, start[i].r, start[i].c, 0);

		printf("#%d %d\n", tc, MAXANS);
	}

	return 0;
}