SW Expert Academy 디저트 카페

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

SW Expert Academy

풀이방법

내가 푼 방식의 아이디어의 핵심은 w, h를 만들어서 방향이 3번일때 부터 w, h만큼 사각형을 만들어 비교하는 방식으로 풀었다.  밑의 그림을 보면 이해가 빠르다.

풀이 방법

그외는 주석을 참고하길 바란다.

---

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int dy[4] = { 1, 1, -1, -1 };
int dx[4] = { 1, -1, -1, 1 };
int tourMap[20][20];
int answer = -1;

bool IsInRange(int y, int x)
{
	if (y >= 0 && y < N && x >= 0 && x < N)
		return true;
	return false;
}

//겹치면 true반환
bool IsOverlap(const vector<int>& haveFood, int food)
{
	for (auto ele : haveFood)
		if (ele == food)
			return true;

	return false;
}

void dfs(int dir, vector<int>food, int y, int x, int w, int h)
{
	//탈출조건 : y, x가 범위를 넘었을 경우
	if (IsInRange(y, x) == false)
		return;

	//다음범위가 범위를 넘는지 확인
	int ny = y + dy[dir];
	int nx = x + dx[dir];
	if (IsInRange(ny, nx) == false)
		return;

	//food가 겹치는지 확인
	int nFood = tourMap[ny][nx];
	if (IsOverlap(food, nFood) == true)
		return;

	if (dir == 0)
	{
		y = ny;
		x = nx;
		w += 1;
		food.push_back(nFood);
	}
	else if (dir == 1)
	{
		y = ny;
		x = nx;
		h += 1;
		food.push_back(nFood);
	}
	//여기서부터는 지금까지 만든 w,h를 가지고 순회가 가능한지 확인
	else if (dir == 2)
	{
		for (int i = 0; i < 2; i++)
		{
			int wh, ndir;
			if (i == 0)
			{
				wh = w;
				ndir = 2;
			}
			else 
			{
				wh = h;
				ndir = 3;
			}

			for (int j = 0; j < wh; j++)
			{
				y += dy[ndir];
				x += dx[ndir];
				
				//범위확인ㅈ
				if (IsInRange(y, x) == false)
					return;

				//음식 확인
				nFood = tourMap[y][x];
				if (IsOverlap(food, nFood) == true)
					return;

				food.push_back(nFood);
			}
		}

		//여기까지 오면 갱신
		answer = max(answer, (int)food.size());

		return;
	}
	//계속 가지고 있는 방향으로 가거나 꺽을수 있다.
	for (int i = 0; i < 2; i++)
		dfs(dir + i, food, y, x, w, h);
}

void solve()
{
	answer = -1;

	//input
	cin >> N;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> tourMap[i][j];

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			//모서리는 풀 필요가 없음 ㅎ
			if (i == 0)
				if (j == 0 || j == N - 1)
					continue;
			if (j == 0)
				if (i == 0 || i == N - 1)
					continue;
			dfs(0, vector<int>(0), i, j, 0, 0);
		}
	}

	cout << answer << '\n';
}

int main()
{
	int testcase;
	cin >> testcase;

	for (int i = 0; i < testcase; i++)
	{
		cout << "#" <<i+1 << " ";
		solve();
	}
	return 0;
}

---

시뮬레이션은 너무 오랜만이라.. 고전했다.