[SWEA] 2105. 디저트 카페

문제 링크

[SWEA] 2105. 디저트 카페

풀이 과정

이동방향은 좌표 하나를 기준으로 우하단, 좌하단, 좌상단, 우상단으로 진행하는 시계 방향으로 잡았습니다.

해당 좌표를 이미 방문했는지를 나타내는 2차원의 visit 배열과, 해당 좌표의 디저트를 이미 먹었는지를 표시하는 1차원의 dessert 배열(디저트 종류는 100 이하의 정수)을 이용했습니다.

함수의 파라미터 dir는 호출한 시점의 방향을 기록한 것으로, 바로 전 호출에서 좌상단으로 진행을 했다면 우하단, 좌하단으로의 진행은 더이상 가지 않습니다.

cnt 가 2일 수는 없기 때문에 갈 수 없는 진행 경로로 칩니다.

코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    static int N;
    static int[][] map;
    static boolean[][] visit;
    static boolean[] dessert;

    static int[] di = {1, 1, -1, -1};
    static int[] dj = {1, -1, -1, 1};

    static int ans;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int TC = sc.nextInt();
        for (int tc = 1; tc <= TC; tc++) {
            ans = -1;

            N = sc.nextInt();
            map = new int[N][N];
            visit = new boolean[N][N];
            dessert = new boolean[101];

            for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                    map[i][j] = sc.nextInt();

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    for (int k = 0; k < N; k++) {
                        Arrays.fill(visit[k], false);
                    }
                    Arrays.fill(dessert, false);

                    dfs(i, j, i, j, 1, 0);
                }
            }

            System.out.println("#" + tc + " " + ans);
        }
    }

    private static void dfs(int si, int sj, int i, int j, int cnt, int dir) {
        if (i == si + 1 && j == sj - 1) {
            if (cnt == 2)
                return;

            ans = Math.max(ans, cnt);
            return;
        }

        visit[i][j] = true;
        dessert[map[i][j]] = true;

        for (int d = dir; d < 4; d++) {
            int ni = i + di[d];
            int nj = j + dj[d];

            if (ni < 0 || ni > N - 1 || nj < 0 || nj > N - 1 || visit[ni][nj] || dessert[map[ni][nj]]) continue;

            dfs(si, sj, ni, nj, cnt + 1, d);
        }

        visit[i][j] = false;
        dessert[map[i][j]] = false;
    }
}