[SWEA]#7733 치즈 도둑

문제

치즈를 좋아하는다혜는 한 변의 길이가 N인 정사각형 모양의 치즈를 샀다.

이 치즈는 특이하게도 N*N개의 모든 칸의 맛있는 정도가 동일하지 않다.

맛있는 정도는 1부터 100 사이로 표현된다.

명우는 치즈를 사서냉동실에 넣어놨는데, 냉동실에는 치즈를 엄청 좋아하는 요정이 숨어있다.

요정은 100일동안 치즈를 갉아먹는데, X번째날에는 맛있는 정도가 X인 칸을 먹어버린다.

치즈 덩어리란상, 하, 좌, 우로인접한 칸들을 하나로 묶어놓은 것을 의미한다.

100일 중에서 치즈덩어리가 가장 많을 때의 덩어리 개수를 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 치즈의 한 변의 길이 N(2 ≤ N ≤ 100)이 주어진다.

이어서 N개의줄에 걸쳐서 각 칸의 맛있는 정도가 1부터 100 사이의숫자로 주어진다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스번호를 의미하며 1부터 시작한다)를 출력하고,

각 테스트 케이스마다 100일 중에서 가장 덩어리가 많을 때의 덩어리 개수를 출력하라.

예제 입력 1

2       // 테스트 케이스 개수
2       // 치즈 한 변의 길이 N
1 2
2 1
5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

예제 출력 1

#1 2  // 첫 번째 테스트 케이스 결과
#2 5

풀이

import java.util.Scanner;
 
class Solution
{
    static int[][] cheese;
    static boolean[][] visited;
    static int[] dx={-1, 1, 0, 0};
    static int[] dy={0, 0, -1, 1};
     
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            int N = sc.nextInt();
            int max = Integer.MIN_VALUE;
            int cnt;
            cheese = new int[N][N];
             
            for(int i=0; i<N; i++) {
                for(int j=0; j<N; j++) {
                    cheese[i][j]=sc.nextInt();
                }
            }
             
            for(int day=0; day<=100; day++) {
                cnt=0;
                visited = new boolean[N][N];
                eat(cheese, day);
                 
                for(int i=0; i<N; i++) {
                    for(int j=0; j<N; j++) {
                        if(visited[i][j]==false && cheese[i][j]!=0) {
                            cnt++;
                            count(i, j);
                        }
                    }
                }
                 
                if(max<cnt)
                    max=cnt;
            }
            System.out.println("#"+test_case+" "+max);
        }
    }
     
    public static void eat(int[][] cheese, int day) {
        for(int i=0; i<cheese.length; i++) {
            for(int j=0; j<cheese.length; j++) {
                if(cheese[i][j]==day) {
                    cheese[i][j]=0;
                    visited[i][j]=true;
                }
            }
        }
    }
     
    public static void count(int X, int Y) {
        int originX=X;
        int originY=Y;
        int x=0;
        int y=0;
         
        visited[originX][originY]=true;
         
        for(int i=0; i<4; i++) {
            x=originX+dx[i];
            y=originY+dy[i];
             
            if(x>=0 && x<cheese.length && y<cheese.length && y>=0 && !visited[x][y] && cheese[x][y]!=0)
                count(x, y);
        }
    }
}