2105. [모의 SW 역량테스트] 디저트 카페

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

class Solution {

static boolean Debug = false;

private static int T;

private static int MapSize;

private static int[][] Map;

private static int MaxSize;

private static int DesertMaxNo;

public static void main(String args[]) throws Exception {

BufferedReader br;

if (Debug) {

File f = new File("C:\\Users\\wvimi\\Downloads", "sample_input (10).txt");

FileReader reader = new FileReader(f);

br = new BufferedReader(reader);

} else {

br = new BufferedReader(new InputStreamReader(System.in)); // 직접입력시 이용

}

StringTokenizer st;

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

for (T = 1; T <= TestSize; T++) {

MapSize = Integer.parseInt(br.readLine());

Map = new int[MapSize][];

DesertMaxNo = -1; 

// Map 읽기

for (int i = 0; i < MapSize; i++) {

Map[i] = new int[MapSize];

st = new StringTokenizer(br.readLine());

for (int j = 0; j < MapSize; j++) {

Map[i][j] = Integer.parseInt(st.nextToken());

if(Map[i][j]>DesertMaxNo) {

DesertMaxNo = Map[i][j];

}

}

}

MaxSize = -1;

findPath();

System.out.println(String.format("#%d %d", T, MaxSize));

}

}

private static void findPath() {

int y, x;

for (int XY = 0; XY < MapSize * MapSize; XY++) {

// 모든 좌표 탐색

y = XY / MapSize;

x = XY % MapSize;

// 최대 이동범위 구하기 (왼쪽, 오른쪽)

int maxLeft = x;

int maxRight = (MapSize - 1) - x;

for (int i = maxLeft; i > 0; i--) {

for (int j = maxRight; j > 0; j--) {

// 수직크기 측정 (맵의 범위를 벗어나지 않도록)

if (i + j + y >= MapSize) {

continue;

}

// 해당 움직임의 디저트수

int eatSize = (i + j) * 2;

if (MaxSize < eatSize) {

// 더 작은 사이즈는 측정할 필요가 없음

if (eatDesert(XY, i, j) == true) {

MaxSize = eatSize;

}

}

}

}

}

}

// 탐색 순서를 고려하여 배치

static int[] rotY = { 1, 1, -1, -1 };

static int[] rotX = { 1, -1, -1, 1 };

private static boolean eatDesert(int XY, int left, int right) {

// XY: 현재좌표, left: 좌로 움직일 수 있는 범위, right: 우로 움직일수 있는 범위

int y = XY / MapSize;

int x = XY % MapSize;

int[] visited = new int[DesertMaxNo+1];

// ↘ 방향 right 번 -> ↙ 방향 left 번 -> ↖ 방향 right 번 -> ↗ 방향 left번

for (int i = 0; i < right; i++) {

y += rotY[0];

x += rotX[0];

if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}

}

for (int i = 0; i < left; i++) {

y += rotY[1];

x += rotX[1];

if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}

}

for (int i = 0; i < right; i++) {

y += rotY[2];

x += rotX[2];

if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}

}

for (int i = 0; i < left; i++) {

y += rotY[3];

x += rotX[3];

if (visited[Map[y][x]]==1) {

return false;

} else {

visited[Map[y][x]] = 1;

}

}

return true;

}

public static void log(String input) {

if (Debug) {

System.out.println(input);

}

}

public static void log(String input, Object... args) {

if (Debug) {

System.out.println(String.format(input, args));

}

}

}