[모의 SW 역량테스트] 디저트 카페 공부

2026-02-24 5 분 소요

1. 문제 접근 방법 및 접근 순서

이 문제는 임의의 한 지점에서 출발해 사각형 모양을 그리며 제자리로 돌아오는 경로 중, 중복되는 디저트 종류 없이 가장 많은 디저트를 먹는 경로를 찾는 것이 핵심입니다.

출발점 설정
- 격자의 모든 칸을 순회하며 출발점으로 설정합니다.
이동 규칙 정의
- 사각형은 반드시 4번의 방향 전환이 필요합니다.
- 대각선 방향: ↘, ↙, ↖, ↗
경로 탐색(DFS)
- 현재 방향을 유지하거나, 다음 방향으로 꺽는 두 가지 선택지를 가지고 탐색을 진행합니다.
조건 체크
- 이동하려는 칸이 격자 안인가?
- 이미 먹은 디저트 종류인가? (중복 체크)
- 출발점으로 돌아왔는가?
최댓값 갱신
- 출발점에 돌아왔을 때, 지금까지 먹은 디저트의 개수를 계삲하여 최댓값을 저장합니다.

2. 문제 해결에 필요한 개념 및 알고리즘

DFS + 백트래킹
- 가능한 모든 사각형의 모양과 크기를 시도해봐야 합니다.
- 경로에 따라가다가 조건에 맞지 않으면 즉시 되돌아와서 다른 길을 찾아야 하므로 백트래킹이 효율적입니다.
방문 배열
- 디저트 번호는 최대 100까지 입니다. 이미 먹은 디저트인지 빠르게 확인하기 위해 boolean 배열을 사용합니다.
- 문제에서 “같은 숫자의 디저트를 팔고 있는 카페가 있어서는 안 된다”는 문구에서 중복 체크용 자료구조의 필요성을 알 수 있습니다.

3. 어려웠던 점

방향 전환 제어
- 방향 전환 제어를 어떻게 해야 하는지 몰라서 시간 복잡도가 어떻게 되는지 파악할 수 없었습니다.
종료 조건
- “출발점으로 정확히 돌아오는가”와 “사각형의 형태를 갖췄는가”를 체크해야 하는지 알 수 없었습니다.

3.1 시간 복잡도

전체 시간복잡도 = 출발점의 개수 * 각 출발점에서 가능한 경로의 수

출발점의 개수
- 격자의 크기가 N*N일 때 모든 칸을 출발점으로 시도하므로 O(N^2)입니다.
각 출발점에서의 경로 탐색 일반적인 DFS는 지수 시간으로 표현되자만, 제약 조건이 매우 강합니다.
- 방향 제한: 오직 4방향 전환만 허용되며, 순서가 정해져 있습니다.
- 사각형의 특징: 한 변의 길이 a, 다른 변의 길이 b가 정해지면 사각형이 되기 위해 경로는 유일하게 결정됩니다.
- 출발점에서 나올 수 있는 사각형의 경우 수는 O(N^2)입니다.
최종 복잡도
- 결과적으로 전체 시간 복잡도는 대략 O(N^2 * N^2) = O(N^4)입니다.

4. 코드 풀이

4.1 출발점 설정

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
					
		Arrays.fill(visited, false);

		// 시작점 저장
		start_r = i;
		start_c = j;

		// 시작점 디저트 카페의 종류 체크
		visited[map[i][j]] = true;

		dfs(i, j, 0, 1);

	}
}

주어진 맵의 모든 영역을 순회하며 출발점으로 설정합니다.

4.2 이동 규칙 정의

static int dr[] = { 1, 1, -1, -1 }; // 행 방향 배열
static int dc[] = { 1, -1, -1, 1 }; // 열 방향 배열

사각형은 반드시 4 방향 전환이 필요합니다.
대각선 방향: ↘, ↙, ↖, ↗

tatic void dfs(int r, int c, int dir, int count) {

	for (int d = dir; d < 4; d++) {

		// 다음 좌표
		int nr = r + dr[d];
		int nc = c + dc[d];
	}
}

경로 탐색을 할 때 현재의 방향을 고정하고, 순회합니다.

4.3 DFS (경로 탐색)

// 범위를 벗어나면 다음으로 넘어간다.
if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
	continue;

이동하려는 칸이 격자 안에 있는지 체크합니다.

// 이미 같은 종류의 카페를 만나면 다음으로 넘어간다.
if (visited[num])
	continue;

이미 먹은 디저트 종류인지 체크합니다.

// 시작점에 도착하고, 최소4개의 카페를 순회하면 계산
if (start_r == nr && start_c == nc && count >= 4) {
	maxCnt = Math.max(maxCnt, count);
	continue;
}

출발점으로 돌아오는지 체크합니다.
출발점에 돌아왔을 때, 지금까지 먹은 디저트의 개수를 계산하여 최댓값을 저장합니다.

4.3.1 DFS 함수 전체 코드

static void dfs(int r, int c, int dir, int count) {

	for (int d = dir; d < 4; d++) {

		// 다음 좌표
		int nr = r + dr[d];
		int nc = c + dc[d];

		// 시작점에 도착하고, 최소4개의 카페를 순회하면 계산
		if (start_r == nr && start_c == nc && count >= 4) {
			maxCnt = Math.max(maxCnt, count);
			continue;
		}

		// 범위를 벗어나면 다음으로 넘어간다.
		if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
			continue;

		// 다음 좌표에 디저트 종류
		int num = map[nr][nc];

		// 이미 같은 종류의 카페를 만나면 다음으로 넘어간다.
		if (visited[num])
			continue;

		// 방문 체크
		visited[num] = true;

		dfs(nr, nc, d, count + 1);

		// 방문 해제
		visited[num] = false;

	}

}

4.4 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution_디저트카페 {

	static int N; // 지역 한 변의 길이
	static int map[][]; // 디저트 종류 정보
	static boolean visited[]; // 디저트 종류 체크 배열
	static int maxCnt; // 디저트를 가장 많이 먹을 때의 디저트 수
	static int start_r, start_c; // 탐색 시작점
	static int dr[] = { 1, 1, -1, -1 }; // 행 방향 배열
	static int dc[] = { 1, -1, -1, 1 }; // 열 방향 배열

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine().trim());

		// tc 수행
		for (int tc = 1; tc <= T; tc++) {

			// 지역 한 변의 길이 입력
			N = Integer.parseInt(br.readLine().trim());
			map = new int[N][N];
			visited = new boolean[101]; // 1 ~ 100 디저트 종류

			// 디저트 종류 정보 입력
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			// 처리
			maxCnt = -1;

			// 지역의 모든 카페를 조사한다.
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					
					Arrays.fill(visited, false);

					// 시작점 저장
					start_r = i;
					start_c = j;

					// 시작점 디저트 카페의 종류 체크
					visited[map[i][j]] = true;

					dfs(i, j, 0, 1);

				}
			}

			// 출력 내용 추가
			sb.append("#" + tc + " " + maxCnt + "\n");
		} // tc 종료

		// 출력
		System.out.println(sb);

	} // 메인 종료

	// 사각형으로 탐색하는 함수
	// 좌표, 방향, 개수
	static void dfs(int r, int c, int dir, int count) {

		for (int d = dir; d < 4; d++) {

			// 다음 좌표
			int nr = r + dr[d];
			int nc = c + dc[d];

			// 시작점에 도착하고, 최소4개의 카페를 순회하면 계산
			if (start_r == nr && start_c == nc && count >= 4) {
				maxCnt = Math.max(maxCnt, count);
				continue;
			}

			// 범위를 벗어나면 다음으로 넘어간다.
			if (!(0 <= nr && nr < N && 0 <= nc && nc < N))
				continue;

			// 다음 좌표에 디저트 종류
			int num = map[nr][nc];

			// 이미 같은 종류의 카페를 만나면 다음으로 넘어간다.
			if (visited[num])
				continue;

			// 방문 체크
			visited[num] = true;

			dfs(nr, nc, d, count + 1);

			// 방문 해제
			visited[num] = false;

		}

	}

}

Twitter Facebook LinkedIn

Lee Jeong Beom

[모의 SW 역량테스트] 디저트 카페 공부

1. 문제 접근 방법 및 접근 순서

2. 문제 해결에 필요한 개념 및 알고리즘

3. 어려웠던 점

3.1 시간 복잡도

4. 코드 풀이

4.1 출발점 설정

4.2 이동 규칙 정의

4.3 DFS (경로 탐색)

4.3.1 DFS 함수 전체 코드

4.4 전체 코드

공유하기

참고

몬스터 헌터

사칙연산 유효성 검사

Map 기본 사용법 및 예제

string 클래스 공부