[SWEA 2105번] 디저트 카페 :: 늦깎이 IT

[SWEA 2105번] 디저트 카페 URL

1. N X N의 Map에서, 가능성이 있는 조합을 모두 찾는다. 예를 들어, 4 X 4의 2차원 배열에서 탐색할 수 있는 칸의 조합은 왼쪽아래, 오른쪽아래, 오른쪽위, 왼쪽위 순서로 탐색했을 때 다음과 같다.

1) 왼쪽아래 2칸 // 오른쪽아래  1칸 // 오른쪽위 2칸 // 왼쪽위 1칸

2) 왼쪽아래 1칸 // 오른쪽아래  2칸 // 오른쪽위 1칸 // 왼쪽위 2칸

3) 왼쪽아래 1칸 // 오른쪽아래  1칸 // 오른쪽위 1칸 // 왼쪽위 1칸

2. 4 X 4 2차원 배열의 어느 지점에서, 1번에서 구했던 각 방향마다의 이동칸수가 가능하다면, 탐색을 시작한다.

탐색할 때에는 디저트의 종류는 1부터 100이므로 boolean형 배열을 선언해서 확인한다.

[소스 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
 
public class Solution {
 
    public static int N, tCase, leftDown, rightDown, ans = 0;
    public static int[][] map;
    public static int[] dirX = new int[] { 1, 1, -1, -1 };
    public static int[] dirY = new int[] { -1, 1, 1, -1 };
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
    public static void main(String[] args) throws Exception {
 
        StringTokenizer st = new StringTokenizer(br.readLine());
        tCase = Integer.parseInt(st.nextToken());
 
        for (int t = 1; t <= tCase; t++) {
 
            st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
 
            map = new int[N][N];
            ans = -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());
                }
            }
 
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    for (int i = N - 2; i >= 1; i--) {
                        for (int j = N - i - 1; j >= 1; j--) {
                            leftDown = i;
                            rightDown = j;
                            solve(row, col, new boolean[101]);
                        }
                    }
                }
            }
            System.out.println("#" + t + " " + ans);
        }
    }
 
    public static void solve(int row, int col, boolean[] visited) {
 
        if (!isPossible(row, col))
            return;
 
        int nr = row;
        int nc = col;
 
        for (int i = 0; i < 4; i++) {
 
            // 왼쪽아래, 오른쪽위
            if (i == 0 || i == 2) {
                for (int j = 1; j <= leftDown; j++) {
                    nr = nr + dirX[i];
                    nc = nc + dirY[i];
                    if (!visited[map[nr][nc]]) {
                        visited[map[nr][nc]] = true;
                    } else
                        return;
                }
            } else { // 오른쪽 아래, 왼쪽위
                for (int j = 1; j <= rightDown; j++) {
                    nr = nr + dirX[i];
                    nc = nc + dirY[i];
                    if (!visited[map[nr][nc]]) {
                        visited[map[nr][nc]] = true;
                    } else
                        return;
                }
            }
        }
        ans = Math.max(ans, rightDown * 2 + leftDown * 2);
 
    }
 
    public static boolean isPossible(int row, int col) {
        int nr = row;
        int nc = col;
 
        nr = nr + dirX[0] * leftDown;
        nc = nc + dirY[0] * leftDown;
        if (!isBoundary(nr, nc))
            return false;
 
        nr = nr + dirX[1] * rightDown;
        nc = nc + dirY[1] * rightDown;
        if (!isBoundary(nr, nc))
            return false;
 
        nr = nr + dirX[2] * leftDown;
        nc = nc + dirY[2] * leftDown;
        if (!isBoundary(nr, nc))
            return false;
 
        nr = nr + dirX[3] * rightDown;
        nc = nc + dirY[3] * rightDown;
        if (!isBoundary(nr, nc))
            return false;
 
        return true;
    }
 
    public static boolean isBoundary(int row, int col) {
        return (row >= 0 && row < N) && (col >= 0 && col < N);
    }
 
    public static void showMap(int[][] map) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println();
    }
}