2105. 디저트 카페

static int N;
static int board[20][20];
static int d[4][2] = {
	1, 1,
	1, -1,
	-1, -1,
	-1, 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 int travel(int y, int x, int j, int k)
{
	int visit[101], ret = 0; 
	int lens[] = { j, k, j, k }; //d의 방향 순서와 동일하게

	memset(visit, 0, sizeof(visit));
	for (int dir = 0; dir < 4; dir++)
	{
		for (int len = 1; len < lens[dir]; len++)
		{
			y += d[dir][0];
			x += d[dir][1];

			if (out_of_bound(y, x))
				return -1; //실패
			if (visit[board[y][x]])
				return -1; //실패

			visit[board[y][x]] = 1; //방문함
			ret += 1;
		}
	}
	return ret;
}

static int solution()
{
	int ans = -1;

	scanf("%d", &N);
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			scanf("%d", &board[y][x]);
		}
	}

	for (int y = 0; y < N - 1; y++)
	{
		for (int x = 1; x < N - 1; x++)
		{
			//우하단, 좌상단 길이
			for (int j = 2; j <= N - 1; j++) 
			{
				//좌하단, 우상단 길이
				for (int k = 2; k <= N - 1; k++)
				{
					//현재 배열에서 만들 수 없는 사각형
					if (j + k > N + 1)
						break;
					int ret = travel(y, x, j, k);
					if (ret > ans)
						ans = ret;
				}
			}
		}
	}

	return ans;
}

최대, 최소 문제 답게 가능한 모든 경우를 다 고려해야 한다.

 

다만 명확하게 순회 할 수 없는 부분은 제외해도 좋다. 

마지막 row라면 더 밑으로 내려 갈 수 없으니 제외해도 되고,

첫번째 column은 처음 위치로 되돌아 올 수 없으니 제외하고, 마지막 column은 시작 위치 그 다음으로 갈 수 없으니 역시 제외해도 된다.

 

이렇게 해서 모든 시작점 (y, x)를 설정 할 수 있다.

 

다음은 문제를 다시 풀면서 제대로 읽지 않았던 부분인데, 사각형 방향으로 순회해야 한다. 여기서 정사각형이라는 조건이 없으므로 가로, 세로 모든 방향을 다 체크해봐야 한다. 

그러나 문제를 다시 풀면서 예전에 풀었던 기억에 의지해 이러한 부분을 놓쳤다.

 

가로, 세로 길이 j와 k를 설정하는 방법이다.

그림을 그려보면 쉽게 알 수 있는데, 어떤 점에서 한 대각선 방향으로는 최대 N - 1 까지만 갈 수 있다.

즉, 가로, 세로 길이 모두 2부터 N - 1 까지 되도록 설정하면 된다.

2부터 시작하는 이유는 한 디저트 카페에만 들르지 않기 때문이다.

 

마지막은 설정한 위치에서 설정한 길이만큼 순회하는 방법이다.

d를 움직이려는 대각선 방향대로 설정하고, 이 순서대로 가로, 세로 길이를 먼저 설정한다.

[↘, ↙, ↖, ↗]

[가, 세, 가, 세]

 

마지막은 주어진 길이만큼 순회해야 하는데,

시작 부터 주어진 길이 만큼 순회하면 그 다음처리가 조금 곤란해진다.

시작 부터 우하단으로 3만큼 이동하면,

그 다음에는 그 위치부터 좌하단으로 4만큼 이동해야 하는 것이 아니라, 3만큼 이동해야 하는 것이다.

 

이 부분은 설정한 길이 보다 1작게 움직이에 함으로서 해결하였다.

이렇게 하면 예외처리를 굳이 할 필요가 없기 때문이다.

 

 

//주의사항 및 정리

1. 문제를 정확히 읽고 무엇을 요구하는지 반드시 캐치할 것. 지금은 예전에 풀었던 기억이 일부 남아있어서 흘려넘기는 경우가 있지만, 이것이 습관이 되면 실제 시험에서도 실수 할 수 있다.

2. for문이 많이 중첩되어도 걱정하지 말 것, 최대 최소는 가급적 모든 경우를 다 탐색해봐야 하기 때문이며, 특정 경우로 단정해서 파악하는 방법은 사실 상 없다. 더구나 배열의 범위가 1000 * 1000 쯤 되게 끔 나오는 경우는 잘 못봤으며, 이렇게 나온다면 최대, 최소를 구하는 식으로는 안 나올 것이다.