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

DFS 백트래킹

문제

문제 링크

풀이

핵심 알고리즘

DFS

• 시간 복잡도: O(T * N^2 * 2^K) — 최악의 경우 모든 시작점(N^2)에서 경로를 탐색하며, 각 단계에서 직진 또는 회전을 선택하지만 유효한 디저트 종류(100개)와 맵 크기에 의해 실제 탐색 범위는 매우 제한적이다.

핵심 아이디어

백트래킹 DFS를 사용하여 가능한 모든 사각형 경로를 탐색한다. 방향 전환 순서를 고정(0~3번 인덱스)하여 시계 방향 혹은 반시계 방향의 폐곡선을 강제하며, 방문 배열을 통해 디저트 중복 여부를 체크하고 시작점에 도달했을 때의 최대 길이를 갱신한다.

① 유효한 시작점 설정 및 탐색 범위 제한

대각선 사각형을 만들기 위해서는 최소 아래로 2칸, 양옆으로 1칸 이상의 공간이 필요하다. 따라서 불필요한 연산을 줄이기 위해 y는 0부터 N-3까지, x는 1부터 N-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);
		}
	}

② 순차적 방향 전환을 이용한 경로 제어

사각형 경로를 완성하기 위해 방향 인덱스 d를 현재 방향(dir) 혹은 다음 방향(dir + 1)으로만 진행하도록 제한한다. 이 방식은 경로가 뒤로 되돌아가는 것을 방지하고, 0->1->2->3 순서의 방향 전환을 통해 반드시 사각형 형태가 되도록 유도하며 다음 단계에서 시작점 회귀를 판단하는 근거가 된다.

for (int d = dir; d <= dir + 1; d++) {
		// dir이 4가 넘어가면 가지치기
		if (d >= 4) break;

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

③ 시작점 회귀 및 결과 갱신

마지막 네 번째 방향(좌상, d==3)으로 이동 중 시작점(sy, sx)에 도달하면 유효한 사각형 경로가 완성된 것으로 간주한다. 이때까지 수집한 디저트의 개수(cnt)를 최대값과 비교하여 갱신하며, 이후 백트래킹을 통해 다른 경로를 계속 탐색한다.

// 현재 방향이 좌상이면서 다음 칸이 시작점일 때
		if (d == 3 && ny == sy && nx == sx) {
			if (cnt > max_count) max_count = cnt;
			return;
		}

④ 디저트 중복 체크 및 백트래킹

이동할 좌표가 맵 내부에 있고 아직 먹어보지 못한 디저트 종류라면 방문 처리를 하고 DFS를 계속한다. 재귀 호출이 끝난 뒤에는 방문 배열을 다시 false로 되돌려(Backtracking), 다른 경로에서 해당 디저트 종류를 다시 고려할 수 있도록 한다.

// 맵 밖
		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;

---

성능

• 메모리 : 5988 KB

• 시간 : 48 ms

코드 (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;
}

---