[SW Expert] [모의 SW 역량테스트] 2105번 디저트 카페 (Java)

SW Expert [모의 SW 역량테스트] 2105번 디저트 카페 : 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWu

 

 

대각선 방향으로 디저트 카페를 탐색하는 문제이다.

특이한 조건이 있다면, 대각선 방향으로 이동하여 사각형 모양을 그리면서 출발할 카페로 돌아와야 한다는 점이다.

이러한 조건으로 탐색하는 범위는 절반으로 줄일 수 있다.

위와 같은 탐색 경로가 있다면, 절반으로 나눠서 위쪽 부분만 구한다면 아래쪽의 경로는 자동으로 나오게 된다.

 

이번 문제에서는 대각선으로 움직이기 때문에 dx, dy를 평소랑 다르게 지정해주었다. ↗, ↘, ↙, ↖ 의 순서로 0, 1, 2, 3으로 지정해주었다.

dfs로 탐색을 했고, 변수로는 해당 인덱스 x, y와 디저트 종류가 들어 있는 set과 움직인 방향을 저장한 path가 있다.

path의 마지막 저장된 변수가 2라면, ↙ 방향으로 움직이는 것으로 판단하여 절반의 탐색이 종료한다.

절반의 탐색이 끝나면 지금까지 움직인 path 정보를 가지고 나머지 경로를 찾는다.

예를 들어 (x, y) = (2, 3)이고 path가 [0, 0, 1, 2]라면,

뒤에 path 변수에 2씩 더 한 값을 dir로 하여 다음 위치 nx, ny를 찾아준다.

path의 뒤에 2개는 무시하게 되므로 (3,2)와 (4,1) 위치를 탐색하여 set에 추가해준다.

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main {
    private static int n, answer;
    private static int[][] map;
    private static int[] dx = {-1, 1, 1, -1};
    private static int[] dy = {1, 1, -1, -1};

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

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

        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            map = new int[n][n];
            answer = -1;

            for (int i = 0; i < n; i++) { // 입력
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            solution();
            System.out.println("#" + t + " " + answer);
        }
    }

    private static void solution() {
        HashSet<Integer> set = new HashSet<>();
        ArrayList<Integer> path = new ArrayList<>();

        for (int i = 1; i < n - 1; i++) {
            for (int j = 0; j < n - 2; j++) {
                set.add(map[i][j]);
                path.add(0);

                dfs(i, j, set, path);

                set.clear();
                path.clear();
            }
        }
    }

    private static void dfs(int x, int y, HashSet<Integer> set, ArrayList<Integer> path) {
        int dir = path.get(path.size() - 1);
        if (dir == 2) {
            int count = addRest(x, y, set, path);
            if (answer < count) answer = count;
            return;
        }

        int nx = x + dx[dir], ny = y + dy[dir];
        if (!isValid(nx, ny) || set.contains(map[nx][ny])) return;

        HashSet<Integer> tSet = new HashSet<>(); // set 복사
        tSet.addAll(set);

        tSet.add(map[nx][ny]); // 다음 디저트 추가

        ArrayList<Integer> tPath = new ArrayList<>(); // path 복사
        tPath.addAll(path);

        tPath.add(dir);
        dfs(nx, ny, tSet, tPath); // 같은 방향 추가로 탐색

        tPath.remove(tPath.size() - 1);
        tPath.add(dir + 1);
        dfs(nx, ny, tSet, tPath); // 방향 꺾어서 탐색
    }

    private static int addRest(int x, int y, HashSet<Integer> set, ArrayList<Integer> path) {
        int nx = x, ny = y, dir;
        
        for (int i = 0; i < path.size() - 2; i++) {
            dir = path.get(i) + 2;
            nx = nx + dx[dir];
            ny = ny + dy[dir];
            if (!isValid(nx, ny) || set.contains(map[nx][ny])) return -1;

            set.add(map[nx][ny]);
        }
        return set.size();
    }

    private static boolean isValid(int x, int y) {
        if (x < 0 || y < 0 || x >= n || y >= n) return false;
        return true;
    }
}