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

문제

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

입력

입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고, 그 다음 줄부터 T개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 디저트 카페가 모여있는 지역의 한 변의 길이 N이 주어진다.

그 다음 N 줄에는 N * N 크기의 디저트 카페에서 팔고 있는 디저트 종류에 대한 정보가 주어진다.

출력

테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.

각 줄은 "#t"로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t는 1부터 시작하는 테스트 케이스의 번호이다)

출력해야 할 정답은 가능한 경우 중 디저트를 가장 많이 먹을 때의 디저트 수 이다.

만약, 디저트를 먹을 수 없는 경우 정답은 -1이다.

예제 입력

10               
4                
9 8 9 8
4 6 9 4
8 7 7 8
4 5 3 5
5                
8 2 9 6 6
1 9 3 3 4
8 2 3 3 6
4 3 4 4 9
7 4 6 3 5
......

예제 출력

#1 6
#2 -1
#3 4
#4 4
#5 8
#6 6
#7 14
#8 12
#9 18
#10 30

풀이

이 문제는 bruteforce로 모든 경우의 수를 구해서 풀 수 있었다.

import java.io.InputStreamReader;
import java.io.BufferedReader;

class Solution
{
    static int[] dx = {1, 1, -1, -1};
    static int[] dy = {1, -1, -1, 1};
    static int N;
    static int[][] map;
    static int max;
    
	public static void main(String args[]) throws Exception
	{
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for(int test_case = 1; test_case <= T; test_case++)
		{
            		N = Integer.parseInt(br.readLine());
            		map = new int[N][N];
            		max = -1;
            
           		for(int i=0; i<N; i++) {
                		String[] input = br.readLine().split(" ");
                		for(int j=0; j<N; j++)
                    			map[i][j] = Integer.parseInt(input[j]);
            		}
  
            		for(int i=0; i<N-2; i++) {
                		for(int j=1; j<N-1; j++) {
                    			for(int r=1; r<N; r++) {
                        			for(int c=1; c<N; c++) {
                            				bruteforce(i, j, r, c);
                        			}
                    			}
                		}
            		}
            		System.out.println("#"+test_case+" "+max);
		}
	}
    
    public static void bruteforce(int x, int y, int r, int c) {
        boolean[] dessert = new boolean[101];
        int nx = x;
        int ny = y;
        int cnt = 0;
        
        for(int idx=0; idx<4; idx++) {
            int i = 0;
            
            if(idx==0 || idx==2) i=r;
            else i=c;
            
            for(int j=0; j<i; j++) {
                nx += dx[idx];
                ny += dy[idx];
                
                if(nx<0 || nx>=N || ny<0 || ny>=N || dessert[map[nx][ny]]) break;
                
                dessert[map[nx][ny]] = true;
                cnt++;
            }
        }
        if(cnt == 2*(r+c))
            max = Math.max(max, 2*(r+c));
    }
}