SW Expert Academy - 2105. 디저트 카페

문제링크

• 디저트 카페

문제설명

• 한 변의 길이가 N인 정사각형 모양을 가진 지역에 디저트 카페가 모여 있다.
• 원 안의 숫자는 해당 디저트 카페에서 팔고 있는 디저트의 종류를 의미하고, 카페들 사이에는 대각선 방향으로 움직일 수 있는 길들이 있다.
• 디저트 카페 투어는 어느 한 카페에서 출발하여 아래 그림과 같이 대각선 방향으로 움직이고 사각형 모양을 그리며 출발한 카페로 돌아와야 한다.

• 하나의 카페에서 디저트를 먹어도 안되며 왔던 길을 다시 돌아가는 것도 안된다.
  • 반드시 사각형을 그려야 한다. 직선도 안된다.
• 가장 많은 디저트를 먹을 수 있는 경로를 찾고, 그 때의 디저트 수를 정답으로 출력하라

문제접근

• 완전탐색 으로 풀었다. 특별한 알고리즘 기법 보다는 구현, 시뮬레이션에 가까운 것 같다.
• 출발점에서 왼쪽 아래 대각선, 오른쪽 아래 대각선 방향으로 나아갈 수 있는 최대 길이를 구한다.
  • 대각선으로 만드는 사각형의 변의 길이가 된다.
  • 대각선으로 만드는 사각형은 직사각형이 되며 두 변이 서로 평행하고 길이가 같다.
• 왼쪽 혹은 오른쪽 아래 대각선으로 나아갈 수 있는 방향이 둘 중 하나라도 0이라면 사각형을 그릴 수 없다.
• 사각형을 그릴 수 있는 경우는 아래와 같은 방법으로 루트를 완성한다.
  • 계산한 left, right 값을 이용하여 그릴 수 있는 모든 사각형을 찾는다.
  • 예를 들어, left=2, right=1 인 경우 만들 수 있는 사각형은 (left=1, right=1), (left=2, right=2) 이렇게 두 가지가 있을 수 있다.
  • 그렇게 정한 루트대로 탐색하며 사각형을 그리는데 이동한 곳의 디저트 종류가 이전에 방문한 카페의 디저트 종류와 같다면 탐색을 중단한다.
• 위 과정을 모든 출발점에 대해 반복한다.

구현

#include <iostream>
#include <vector>
#include <memory.h>
#include <algorithm>

#define MAX_N 20
using namespace std;

int N, ans = -1;
int board[MAX_N][MAX_N];
//  왼쪽 아래 대각선, 오른쪽 아래 대각선 방향으로만 움직인다.
int dx[2] = { 1, 1 };
int dy[2] = { -1, 1 };

void makeBox(int startX, int startY, int left, int right) {
	vector<int> history;
	history.push_back(board[startX][startY]);

	// 시작점에서 왼쪽으로 left 칸만큼 이동
	int cx = startX, cy = startY;
	for (int i = 0; i < left; i++) {
		int nx = cx + dx[0];
		int ny = cy + dy[0];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return;
		// 이미 먹었던 디저트 종류라면 반환
		if (find(history.begin(), history.end(), board[nx][ny]) != history.end()) return;
		history.push_back(board[nx][ny]);
		cx = nx; cy = ny;
	}

	// 이동한 점에서 오른쪽 아래로 이동
	for (int i = 0; i < right; i++) {
		int nx = cx + dx[1];
		int ny = cy + dy[1];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return;
		// 이미 먹었던 디저트 종류라면 반환
		if (find(history.begin(), history.end(), board[nx][ny]) != history.end()) return;
		history.push_back(board[nx][ny]);
		cx = nx; cy = ny;
	}

	// 시작점에서 오른쪽 아래로 이동
	cx = startX; cy = startY;
	for (int i = 0; i < right; i++) {
		int nx = cx + dx[1];
		int ny = cy + dy[1];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return;
		// 이미 먹었던 디저트 종류라면 반환
		if (find(history.begin(), history.end(), board[nx][ny]) != history.end()) return;
		history.push_back(board[nx][ny]);
		cx = nx; cy = ny;
	}

	// 이동한 점에서 왼쪽 아래로 이동
	// 마지막 이동이므로 left - 1 만큼 이동
	for (int i = 0; i < left - 1; i++) {
		int nx = cx + dx[0];
		int ny = cy + dy[0];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return;
		// 이미 먹었던 디저트 종류라면 반환
		if (find(history.begin(), history.end(), board[nx][ny]) != history.end()) return;
		history.push_back(board[nx][ny]);
		cx = nx; cy = ny;
	}

	ans = max(ans, (int)history.size());
}

void visitCafes(int startX, int startY, int left, int right) {
	for (int i = 1; i <= left; i++) {
		for (int j = 1; j <= right; j++) {
			makeBox(startX, startY, i, j);
		}
	}
}

void setCrossLength(int startX, int startY, int& left, int& right) {
	// 왼쪽 아래 대각선으로 갈 수 있는 최대 길이
	int cx = startX, cy = startY;
	while (true) {
		int nx = cx + dx[0];
		int ny = cy + dy[0];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;
		left++;
		cx = nx; cy = ny;
	}

	// 오른쪽 아래 대각선으로 갈 수 있는 최대 길이
	cx = startX, cy = startY;
	while (true) {
		int nx = cx + dx[1];
		int ny = cy + dy[1];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) break;
		right++;
		cx = nx; cy = ny;
	}
}

void goDessertCafe(int startX, int startY) {
	int left = 0, right = 0;
	setCrossLength(startX, startY, left, right);

	// 대각선을 만들 수 없는 경우
	if (left == 0 || right == 0) return;

	// 대각선을 만들 수 있는 경우
	visitCafes(startX, startY, left, right);
}

int main(int argc, char** argv)
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		memset(board, 0, sizeof(board));
		cin >> N;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				cin >> board[r][c];
			}
		}
		ans = -1;
		for (int r = 0; r < N; r++) {
			for (int c = 0; c < N; c++) {
				goDessertCafe(r, c);
			}
		}
		printf("#%d %d\n", test_case, ans);
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

구현2

#include <iostream>
#include <memory.h>
#include <set>
#include <algorithm>
#define MAX_N 20
#define UP_RIGHT 0
#define DOWN_RIGHT 1
#define UP_LEFT 2
#define DOWN_LEFT 3
using namespace std;

int N;
int board[MAX_N][MAX_N];
int dx[4] = { -1, 1, -1, 1 };
int dy[4] = { 1, 1, -1, -1 };
set<int> cand;

void input()
{
	cin >> N;
	for (int r = 0; r < N; r++) {
		for (int c = 0; c < N; c++) {
			cin >> board[r][c];
		}
	}
}

bool move(int& xpos, int& ypos, int dir, int len)
{
	int nx = xpos;
	int ny = ypos;
	for (int i = 0; i < len - 1; i++) {
		nx += dx[dir];
		ny += dy[dir];
		if (nx < 0 || nx >= N || ny < 0 || ny >= N) return false;
		cand.insert(board[nx][ny]);
		xpos = nx;
		ypos = ny;
	}
	return true;
}

bool makeRoute(int cx, int cy, int aLen, int bLen)
{
	cand.clear();
	cand.insert(board[cx][cy]);
	if (move(cx, cy, UP_RIGHT, aLen) == false) return false;
	if (move(cx, cy, DOWN_RIGHT, bLen) == false) return false;
	if (move(cx, cy, DOWN_LEFT, aLen) == false) return false;
	if (move(cx, cy, UP_LEFT, bLen) == false) return false;
	if (cand.size() < aLen * 2 + (bLen - 2) * 2) return false;
	return true;
}

int solution()
{
	int ret = -1;
	for (int a = N - 1; a >= 2; a--) {
		int limit = N - a + 1;
		for (int b = 2; b <= limit; b++) {
			for (int r = 0; r < N; r++) {
				for (int c = 0; c < N; c++) {
					if (makeRoute(r, c, a, b)) {
						ret = max(ret, (int)cand.size());
					}
				}
			}
		}
	}
	return ret;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 0;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	// test();
	for (test_case = 1; test_case <= T; ++test_case)
	{
		input();
		cout << "#" << test_case << " " << solution() << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}