[SWEA] 2105번: ［모의 SW 역량테스트］ 디저트 카페 (Unrated) - C++ 풀이

DFS 백트레킹

💾 메모리: 5,988 KB, 시간: 48 ms, 코드길이: 1,604 Bytes📅 2026-04-09 03:36 > 출처: SW Expert Academy, https://swexpertacademy.com/main/code/problem/problemList.do

문제 링크

코드 (C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>

using namespace std;

int map[20][20];
// 디저트 종류는 최대 100번
bool visited[101];
int N, max_count;
int sy, sx;

// 방향: {좌하, 우하, 우상, 좌상}
int dy[4] = { 1, 1, -1, -1 };
int dx[4] = { -1, 1, 1, -1 };

void dfs(int y, int x, int dir, int cnt) {
	// 현재 방향으로 직진하거나 90도 꺾어서 진행
	for (int d = dir; d <= dir + 1; d++) {
		// dir이 4가 넘어가면 가지치기
		if (d >= 4) break;

		int ny = y + dy[d];
		int nx = x + dx[d];

		// 현재 방향이 좌상이면서 다음 칸이 시작점일 때
		if (d == 3 && ny == sy && nx == sx) {
			if (cnt > max_count) max_count = cnt;
			return;
		}
		// 맵 밖
		if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
		// 이미 먹은 디저트 스킵
		if (visited[map[ny][nx]]) continue;

		// 방문 처리
		visited[map[ny][nx]] = true;
		dfs(ny, nx, d, cnt + 1);
		visited[map[ny][nx]] = false;
	}
}
void solve() {
	max_count = -1;

	// 대각선으로 마름모가 만들어지려면 최소 양 옆 1칸, 아래 2칸이 필요함
	for (int y = 0; y < (N - 2); y++) {
		for (int x = 1; x < (N - 1); x++) {
			// 매번 초기화
			memset(visited, false, sizeof(visited));
			sy = y;
			sx = x;

			visited[map[y][x]] = true;
			// 시작 좌표, 시작방향, 디저트 개수
			dfs(sy, sx, 0, 1);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("test.txt", "r", stdin);
	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {
		cin >> N;

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

		solve();
		
		cout << "#" << tc << " " << max_count << "\n";
	}
	return 0;
}