[SWEA] 2105번 : 디저트 카페

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu&categoryId=AV5VwAr6APYDFAWu&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=2

SW Expert Academy

 

문제

 

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.

 

출력

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

 

---

소스코드

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

class Solution {
    static int arr[][];
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int t = Integer.parseInt(br.readLine());

        for (int i = 0; i < t; i++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];
            for (int j = 0; j < n; j++) {
                st = new StringTokenizer(br.readLine());
                for (int k = 0; k < n; k++) {
                    arr[j][k] = Integer.parseInt(st.nextToken());
                }
            }

            result = -1;
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    desert = new boolean[101];
                    visited = new boolean[n][n];
                    desert[arr[j][k]] = true;
                    visited[j][k] = true;
                    dfs(j, k, j, k, 0, 1);
                }
            }

            sb.append("#" + (i + 1) + " " + result + "\n");
        }
        System.out.println(sb);
    }

    static int rx[] = {1, 1, -1, -1};
    static int ry[] = {1, -1, -1, 1};
    static boolean visited[][];
    static boolean desert[];
    static int result;

    static void dfs(int x, int y, int startX, int startY, int dir, int count) {
        for (int i = dir; i <= dir + 1; i++) {
            if (i == 4) break;
            int nx = x + rx[i];
            int ny = y + ry[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;

            // 시작 점으로 돌아온 경우
            if (nx == startX && ny == startY) {
                if (result < count) result = count;
                return;
            }

            if (desert[arr[nx][ny]]) continue;
            if (visited[nx][ny]) continue;

            visited[nx][ny] = true;
            desert[arr[nx][ny]] = true;
            dfs(nx, ny, startX, startY, i, count + 1);
            desert[arr[nx][ny]] = false;
            visited[nx][ny] = false;
        }
    }
}

 

해결 방법

1. 모든 디저트 카페에서 DFS 탐색을 진행한다.
2. 탐색 방향은 ↘, ↙, ↖, ↗ 순으로 진행된다. 탐색을 할 때 현재 방향, 다음 방향순으로 탐색한다. (현재 탐색 방향이 ↘라면 다음 방향인 ↙까지 탐색해야 한다.) 
3. 탐색은 백트래킹으로 이뤄진다. 고로, 방문 지점과 디저트 종류의 방문 처리를 해줘야 한다.
4. 다음 카페가 시작 점인 경우 result보다 현재 count가 더 크다면 result를 갱신한다.