[SWEA 2105] 디저트카페

문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

💻 문제 풀이 : C++

#include <iostream>
#include <cstring>

#define MAX_MAP_SIZE 25
#define MAX_DESSERT 105

using namespace std;

int N;
int MAP[MAX_MAP_SIZE][MAX_MAP_SIZE];
int dessert[MAX_DESSERT];
int maxLen;

// 시계방향
int dr[4] = { 1, 1, -1, -1 };
int dc[4] = { 1, -1, -1, 1 };

int getMax(int a, int b)
{
	return a > b ? a : b;
}

void CLEAR()
{
	N = 0;
	maxLen = 0;
	memset(MAP, 0, sizeof(MAP));
	memset(dessert, 0, sizeof(dessert));
}

void INPUT()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> MAP[i][j];
		}
	}
}

void DFS(int start_row, int start_col, int now_row, int now_col, int dir, int len)
{
	if (start_row == now_row && start_col == now_col && dir == 3)
	{
		maxLen = getMax(len, maxLen);
		return;
	}

	for (int i = dir; i < 4; i++)
	{
		int next_row = now_row + dr[i];
		int next_col = now_col + dc[i];
		if (next_row < 0 || next_col < 0 || next_row >= N || next_col >= N) continue;
		if (dessert[MAP[next_row][next_col]] == 1) continue;
		dessert[MAP[next_row][next_col]] = 1;
		DFS(start_row, start_col, next_row, next_col, i, len + 1);
		dessert[MAP[next_row][next_col]] = 0;
	}
}

void SOLVE()
{
	// 4방향 탐색(dir == 4)
	// 같은곳으로 돌아오면 종료
	// 종료될때 최대 길이 재기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			DFS(i, j, i, j, 0, 0);
		}
	}
}

int main()
{
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++)
	{
		CLEAR();
		INPUT();
		SOLVE();

		if (maxLen < 4)
			cout << "#" << tc << " -1" << endl;
		else
			cout << "#" << tc << " " << maxLen << endl;
	}

	return 0;
}

📌 memo 😊

• back-tracking 형태를 사용한 이유 ?

dessert[MAP[next_row][next_col]] = 1;

dessert[MAP[next_row][next_col]] = 0;

-> 모든 case를 탐색하기 위함

• DFS params에 direction을 반영 ?

for (int i = dir; i < 4; i++)

DFS(start_row, start_col, next_row, next_col, i, len + 1);

-> 바뀌는 dir을 바로 for문에 적용하기 위함!