SWEA 2105 디저트 카페 (Java)

재귀와 반복문, 델타를 이용한 DFS & 방문체크

• Java

import java.util.Scanner;

class Solution {
    static int N, maxi, row, col;
    static int[][] arr;
    static int[] dr = {1, 1, -1, -1};	// 우하, 좌하, 좌상, 우상
    static int[] dc = {1, -1, -1, 1};
    static boolean[] visited;			// 방문체크
    
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		int T=sc.nextInt();

		for(int test_case = 1; test_case <= T; test_case++) {
            N = sc.nextInt();
            arr = new int[N][N];
            for(int i = 0; i < N; i++) {
            	for(int j = 0; j < N; j++) {
                	arr[i][j] = sc.nextInt();
                }
            }
            maxi = -1;
            for(int i = 0; i < N - 2; i++) {
            	for(int j = 1; j < N - 1; j++) {
                    row = i; 
                    col = j;
                    visited = new boolean[101];
                    visited[arr[i][j]] = true;
                    dfs(0, 0, i, j, -1, -1);
                }
            }
            System.out.println("#" + test_case + " " + maxi);
		}
	}
    static void dfs(int delta, int cnt, int r1, int c1, int r0, int c0) {
        for(int d = delta; d < 4; d++) {
            int r2 = r1 + dr[d];
            int c2 = c1 + dc[d];
            
            // 인덱스 범위를 벗어났을 때
            if(r2 >= N || r2 < 0 || c2 >= N || c2 < 0) continue;
            // 왔던 길로 돌아왔을 때
            if(r2 == r0 && c2 == c0) continue;
            // 초기 위치로 돌아왔을 때
            if(r2 == row && c2 == col) {
                maxi = Math.max(maxi, cnt + 1);
                return;
            }
            // 이미 체크했을 때
            if(visited[arr[r2][c2]]) continue;
            // 모든 조건 충족 시
            visited[arr[r2][c2]] = true;
            dfs(d, cnt + 1, r2, c2, r1, c1);
            visited[arr[r2][c2]] = false;
        }
        
    }
}