[SWEA/Java] 디저트 카페 (2105)

디저트 카페 (2105)

1. 문제 분석

문제 개요:

• N x N 크기의 디저트 카페에서 대각선 방향으로 이동하며 디저트를 먹을 수 있는 최대한의 경로를 찾는 문제이다. 같은 디저트를 두 번 먹으면 안 되고, 처음 위치로 돌아오는 경로를 만들어야 한다.

입력 형식:

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스의 첫 줄에 N이 주어지며, 다음 N개의 줄에 N x N 크기의 카페 정보가 주어진다. 카페 정보는 1부터 100까지의 정수로 주어지며, 각 숫자는 해당 카페에서 제공하는 디저트를 나타낸다.

출력 형식:

• 각 테스트 케이스에 대해 "#"과 테스트 케이스 번호, 그리고 얻을 수 있는 디저트의 최대 개수를 출력한다. 만약 가능한 경로가 없으면 -1을 출력한다.

2. 알고리즘 종류

• DFS(깊이 우선 탐색) 알고리즘을 사용하여 모든 가능한 경로를 탐색한다. 재귀적으로 대각선 방향으로 이동하며 조건을 만족하는 최대 경로를 찾는다.

3. 주요 부분 및 코드 작성 방법

1. DFS(깊이 우선 탐색) 사용:

• DFS를 사용하여 출발점에서 시작해 대각선 방향으로 이동하며 가능한 모든 경로를 탐색한다. 이때, 이미 방문한 카페나 같은 디저트를 두 번 먹는 경우는 제외한다.

2. 대각선 방향 이동:

• 4개의 대각선 방향(↘, ↙, ↖, ↗)으로 이동할 수 있도록 설정한다. 각 방향으로 이동하면서 경로를 갱신한다.

3. 경로 탐색 종료 조건:

• 처음 출발점으로 돌아오는 경로를 찾고, 최소한 4개 이상의 카페를 방문한 경우에만 경로를 유효하게 인정한다.

4. 코드 설명

(1) 메인 함수 (main):

• 입력 처리 및 배열 초기화:

    N = Integer.parseInt(br.readLine()); // 카페 크기 입력
    cafe = new int[N][N]; // 카페 정보 배열 초기화

  • 카페 크기와 정보를 입력받고 배열을 초기화한다.

• DFS를 통한 경로 탐색 및 최대값 갱신:

    answer = -1; // 가능한 경로가 없는 경우를 대비해 -1로 초기화
    for (int i = 0; i < N - 2; i++) {
        for (int j = 1; j < N - 1; j++) {
            visited = new boolean[N][N]; // 방문 기록 초기화
            dessertVisited = new boolean[101]; // 디저트 종류 방문 기록 초기화
            dfs(i, j, i, j, 0, 1); // DFS를 사용해 경로 탐색
        }
    }

  • 시작 가능한 모든 지점에서 DFS를 시작해 최적의 경로를 탐색한다.

• 결과 출력:

    System.out.println("#" + tc + " " + answer); // 테스트 케이스 번호와 함께 결과 출력

  • 테스트 케이스 번호와 함께 탐색된 최대 디저트 수를 출력한다.

(2) DFS 함수 (dfs):

• 초기화 및 방문 기록:

    visited[r][c] = true; // 현재 위치 방문 처리
    dessertVisited[cafe[r][c]] = true; // 해당 디저트 방문 처리

  • 현재 위치와 디저트의 방문 여부를 기록한다.

• 4방향 탐색 및 경로 갱신:

    for (int i = dir; i < 4; i++) { // 대각선 방향으로 탐색
        int nr = r + dr[i]; // 다음 행
        int nc = c + dc[i]; // 다음 열
  
        if (nr == startR && nc == startC && count >= 4) { // 시작점으로 돌아오고 최소 4개의 카페를 방문한 경우
            answer = Math.max(answer, count); // 최대 경로 길이 갱신
            return;
        }
  
        if (nr < 0 || nc < 0 || nr >= N || nc >= N || visited[nr][nc] || dessertVisited[cafe[nr][nc]]) { // 경계 조건 및 방문 여부 확인
            continue; // 조건에 맞지 않으면 다음 방향 탐색
        }
  
        dfs(nr, nc, startR, startC, i, count + 1); // 재귀 호출을 통해 경로 탐색
        visited[nr][nc] = false; // 백트래킹을 위해 방문 기록 제거
        dessertVisited[cafe[nr][nc]] = false; // 디저트 방문 기록 제거
    }

  • 4방향으로 이동하며 경로를 탐색하고, 유효한 경로일 경우 최대값을 갱신한다.

5. 전체 코드

package SWEA.Day0829.SWEA디저트_카페;

import java.io.*;
import java.util.*;

public class SWEA2105 {
    static int N, answer;
    static int[][] cafe; // 카페 정보 배열
    static boolean[][] visited; // 카페 방문 기록
    static boolean[] dessertVisited; // 디저트 방문 기록

    // 대각선 방향 (↘, ↙, ↖, ↗)
    static int[] dr = {1, 1, -1, -1}; // 행 이동량
    static int[] dc = {1, -1, -1, 1}; // 열 이동량

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 입력을 받기 위한 BufferedReader 객체 생성
        int T = Integer.parseInt(br.readLine()); // 테스트 케이스 수 입력

        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine()); // 카페 크기 입력
            cafe = new int[N][N]; // 카페 정보 배열 초기화

            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    cafe[i][j] = Integer.parseInt(st.nextToken()); // 카페 정보 입력
                }
            }

            answer = -1; // 가능한 경로가 없는 경우를 대비해 -1로 초기화
            for (int i = 0; i < N - 2; i++) {
                for (int j = 1; j < N - 1; j++) {
                    visited = new boolean[N][N]; // 방문 기록 초기화
                    dessertVisited = new boolean[101]; // 디저트 종류 방문 기록 초기화
                    dfs(i, j, i, j, 0, 1); // DFS를 사용해 경로 탐색
                }
            }

            System.out.println("#" + tc + " " + answer); // 테스트 케이스 번호와 함께 결과 출력
        }
    }

    public static void dfs(int r, int c, int startR, int startC, int dir, int count) {
        visited[r][c] = true; // 현재 위치 방문 처리
        dessertVisited[cafe[r][c]] = true; // 해당 디저트 방문 처리

        for (int i = dir; i < 4; i++) { // 대각선 방향으로 탐색
            int nr = r + dr[i]; // 다음 행
            int nc = c + dc[i]; // 다음 열

            if (nr == startR && nc == startC && count >= 4) { // 시작점으로 돌아오고 최소 4개의 카페를 방문한 경우
                answer = Math.max(answer, count); // 최대 경로 길이 갱신
                return;
            }

            if (nr < 0 || nc < 0 || nr >= N || nc >= N || visited[nr][nc] || dessertVisited[cafe[nr][nc]]) { // 경계 조건 및 방문 여부 확인
                continue; // 조건에 맞지 않으면 다음 방향 탐색
            }
            dfs(nr, nc, startR, startC, i, count + 1); // 재귀 호출을 통해 경로 탐색
            visited[nr][nc] = false; // 백트래킹을 위해 방문 기록 제거
            dessertVisited[cafe[nr][nc]] = false; // 디저트 방문 기록 제거
        }
    }
}