SWEA 2105 : 디저트 카페 (모의 SW 역량테스트)

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

디저트 카페 링크

 

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

 

MAP의 좌표는 (1, 1)부터 시작하도록 입력을 받는다.

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

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

 

움직일 수 있는 길은 오른쪽 아래부터 시작하여 시계 방향이므로, dr, dc를 잘 mapping 시킨다.

반드시 시계 방향으로 정의해야 한다.

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

 

매 tc마다 dir = 0 (오른쪽 아래)부터 시계 방향으로 길을 잘 만들어가면 된다.

dessert 배열에는 먹은 디저트를 표시한다. 

가장 작은 마름모를 고려하여 r = N - 2까지만 탐색하고, column은 2 ~ N - 1까지만 조사해보면 된다.

for (int tc = 1; tc <= T; tc++)
{
	input();

	MAXANS = -1;
	for (int r = 1; r <= N - 2; r++)
	{
		for (int c = 2; c <= N - 1; c++)
		{
			dessert[MAP[r][c]] = 1;
			DFS(1, r + 1, c + 1, r, c, 0);
			dessert[MAP[r][c]] = 0;
		}
	}

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

 

매번 DFS는 가던 방향을 계속 가거나, 시계 방향으로 방향을 변경할 수 있다.

 

종료 조건은 아래와 같다.

 

1) dir == 4 (방향을 네 번 바꾼 경우)

2) MAP의 범위를 벗어나는 경우

3) 이미 선택한 디저트를 먹은 경우

4) 무사히 도착한 경우 → MAXANS 갱신 (많이 먹은 디저트 수)

 

먹지 않은 디저트의 경우에만 가던 방향을 계속가서나 시계 방향으로 변경해주고,

그 외에 종료 조건을 넣어주면 DFS는 완성된다.

void DFS(int L, int R, int C, int sr, int sc, int dir)
{
	/* 1) dir == 4 (방향을 네 번 바꾼 경우) */
	if (dir == 4) return;

	/* 4) 무사히 도착한 경우 → MAXANS 갱신 */
	if (R == sr && C == sc)
	{
		if (MAXANS < L) MAXANS = L;
		return;
	}

	/* 2) MAP의 범위를 벗어나는 경우 */
	if (R > N || C > N || R < 1 || C < 1) return;

	if (dessert[MAP[R][C]] == 0)
	{
		dessert[MAP[R][C]] = 1;

		/* 현재 방향으로 진행 */
		DFS(L + 1, R + dr[dir], C + dc[dir], sr, sc, dir); 

		/* 시계 방향으로 진행 */
		DFS(L + 1, R + dr[dir + 1], C + dc[dir + 1], sr, sc, dir + 1);

		dessert[MAP[R][C]] = 0;
	}
	else /* 3) 이미 선택한 디저트를 먹은 경우 */
		return;
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (25 + 5)

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

int dessert[100 + 20];
int MAXANS;

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

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

void DFS(int L, int R, int C, int sr, int sc, int dir)
{
	if (dir == 4) return;

	if (R == sr && C == sc)
	{
		if (MAXANS < L) MAXANS = L;
		return;
	}

	/* MAP의 범위를 벗어나는 경우 */
	if (R > N || C > N || R < 1 || C < 1) return;

	if (dessert[MAP[R][C]] == 0)
	{
		dessert[MAP[R][C]] = 1;

		/* 현재 방향으로 진행 */
		DFS(L + 1, R + dr[dir], C + dc[dir], sr, sc, dir); 

		/* 시계 방향으로 진행 */
		DFS(L + 1, R + dr[dir + 1], C + dc[dir + 1], sr, sc, dir + 1);

		dessert[MAP[R][C]] = 0;
	}
	else
		return;
}

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

		MAXANS = -1;
		for (int r = 1; r <= N - 2; r++)
		{
			for (int c = 2; c <= N - 1; c++)
			{
				dessert[MAP[r][c]] = 1;
				DFS(1, r + 1, c + 1, r, c, 0);
				dessert[MAP[r][c]] = 0;
			}
		}

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

	return 0;
}