문제

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

코드 (Java)

import java.util.*;
import java.io.*;

class Solution
{
	private static int[][] cafes;
	private static int[][] delta = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;
		T=Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			int N = Integer.parseInt(br.readLine().trim());
			cafes = new int[N][N];
			
			for (int row = 0; row < N; ++row) {
				StringTokenizer st = new StringTokenizer(br.readLine().trim());
				for (int col = 0; col < N; ++col) {
					cafes[row][col] = Integer.parseInt(st.nextToken());
				}
			} 
			
			//we bruteforce our way to search all cases.
			int posMax = -1;
			for (int row = 0; row < N-2; ++row) {
				for (int col = 1; col < N-1; ++col) {
					//possible edges of rectangle? it depends on current top position of rectangle.
					for (int edge = 2; edge < N - row ; ++edge) {
						if (posMax > 2*edge) continue;
						for (int right = 1; right < edge; ++right) {
							int left = edge - right;
							if (col+right >= N || col - left < 0) {
								continue;
							}
							if (solve(row, col, right, left)) {
								posMax = Math.max(edge*2, posMax);
//								System.out.printf("hit for %d row, %d col, %d right, %d left\n", row, col, right, left);
								break;
							}
//							System.out.printf("failed for %d row, %d col, %d right, %d left\n", row, col, right, left);
						}
					}
				}
			}
			
			bw.write("#" + test_case + " " + posMax + "\n");
		}
		
		bw.flush();
		bw.close();
	}
	
	private static boolean solve(int row, int col, int rightLen, int leftLen) {
		boolean[] ate = new boolean[101];
		for (int i = 0; i < rightLen; ++i) {
			row += delta[0][0];
			col += delta[0][1];
			if (ate[cafes[row][col]]) {
				return false;
			} else {
				ate[cafes[row][col]] = true;
			}
		}
		for (int i = 0; i < leftLen; ++i) {
			row += delta[1][0];
			col += delta[1][1];
			if (ate[cafes[row][col]]) {
				return false;
			} else {
				ate[cafes[row][col]] = true;
			}
		}
		for (int i = 0; i < rightLen; ++i) {
			row += delta[2][0];
			col += delta[2][1];
			if (ate[cafes[row][col]]) {
				return false;
			} else {
				ate[cafes[row][col]] = true;
			}
		}
		for (int i = 0; i < leftLen; ++i) {
			row += delta[3][0];
			col += delta[3][1];
			if (ate[cafes[row][col]]) {
				return false;
			} else {
				ate[cafes[row][col]] = true;
			}
		}
		
		
		return true;
	}
}

풀이

• 역시나 모든 경우의 수를 고려하는 문제(...)

• 모든 경우의 수를 고려해도 계산해보면 생각보다 고려해야하는 개수가 적다. 일단 최대의 경우만 계산하면 되니 한번 특정 길이에 대해서 확인이 되면 그 길이에 대해서 확인을 하지 않아도 된다는 것이 첫번째 특징.

• 그리고 사각형으로만 돌아야 한다. 그래서 우/좌변의 길이가 고정이 되고 이를 활용해가지고 각 지점에서 가능한 사각형들에 대해서 전부 확인해보면 된다. 이때 기준을 위쪽 꼭지점으로 했다. 해당 꼭지점에서 위로 올라가는 형태의 사각형은 사실 아래로 가는 형태만 다 고려하면 자동으로 포함되어서 위쪽 꼭지점을 기준으로 좌/우로 얼만큼 내려갔다 올라갔냐만 고려하면 된다.

• 또 사각형이 좌/우로 이탈을 할 수 있는지, 그리고 밑으로 내려갈 수 있는 최대 길이는 얼마인지도 다 추적을 해야 한다는 점 유의.