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

2차원 배열에서 4개의 점을 정하고 그 점에 있는 값들을 확인 하는 문제입니다. 이 문제에서 핵심은 4개의 점을 정하는 것인데 제가 예전에 정리한 적이 있었던 삼성 기출 문제인 게리멘더링2 ( https://daily-life-of-bsh.tistory.com/130 ) 를 참고하시면 될 것 같습니다.

4개의 점을 정하고 문제를 풀면서 제가 실수했던 부분은 한번의 for문으로 1번점에서 2번점까지 왼쪽 대각선 아래로 가면서 값을 확인하는 동시에 4번 점에서 3번 점으로 오른쪽 위로 올라가면서 값을 확인하려고 했습니다. 하지만 이렇게 하게 되면 1번 -> 2번으로 가는 길과 4번 -> 3번으로 가는 길에 동시에 같은값이 있으면 그것을 잡아내지 못했습니다. 그래서 각각의 방향을 가는 독립적인 for 문 4번을 통해서 해결할 수 있었습니다.

---

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

public class Solution {

	static int[][] map;
	static int N, len, answer;
	static int[] check;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		for(int tc=1; tc<=T; tc++) {
			
			N = sc.nextInt();
			answer = Integer.MIN_VALUE;
			map = new int[N][N];
			
			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-2; i++) {
				for(int j=1; j<N-1; j++) {
					for(int d1=1; d1<=j; d1++) {
						for(int d2=1; d2<N-j; d2++) {
							// i, j : 1번좌표
							// i+d1, j-d1 : 2번좌표
							// i+d2, j+d2 : 3번좌표
							// 2번의 x좌표 + d2, 3번의 y좌표 - d1 : 4번좌표 
							
							if(isInside(i+d1, j+d2) && isInside(i+d1+d2, j+d2-d1)) {
								check = new int[101];
								len = 0;
								
								if(touring(i, j, d1, d2)) answer = Math.max(answer, len);
							}
						}
					}
				}
			}
			if(answer == Integer.MIN_VALUE) answer = -1;
			System.out.println("#" + tc + " " + answer);
		}
	}
	
	public static boolean touring(int x, int y, int d1, int d2) {
		int x2 = x+d1, y2 = y-d1;
		int x3 = x+d2, y3 = y+d2;
		int x4 = x2+d2, y4 = y3-d1;
		
		// 1번에서 2번
		for(int i=0; i<d1; i++) {
			if(check[map[x+i][y-i]] == 0) {
				check[map[x+i][y-i]]++;
				len++;
			} else return false;
		}
		
		// 4번에서 3번
		for(int i=0; i<d1; i++) {
			if(check[map[x4-i][y4+i]] == 0 ) {
				check[map[x4-i][y4+i]]++;
				len++;
			} else return false;
		}
		
		// 2번에서 4번
		for(int i=0; i<d2; i++) {
			if(check[map[x2+i][y2+i]] == 0) {
				check[map[x2+i][y2+i]]++;
				len++;
			} else return false;
		}
		
		// 3번에서 1번
		for(int i=0; i<d2; i++) {
			if(check[map[x3-i][y3-i]] == 0) {
				check[map[x3-i][y3-i]]++;
				len++;
			} else return false;
		}
		
		return true;
	}
	
	public static boolean isInside(int x, int y) {
		return x>=0 && x<N && y>=0 && y<N;
	}

}