SWEA 7733 치즈 도둑(JAVA) 🧀

문제 링크

SW Expert Academy

문제 설명

치즈덩어리가 가장 많을 때의 덩어리 개수 구하기

치즈덩어리(상, 하, 좌, 우로 인접한 칸들을 하나로 묶어놓은 것)

입력

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 치즈의 한 변의 길이 N(2 ≤ N ≤ 100)이 주어진다.
이어서 N개의줄에 걸쳐서 각 칸의 맛있는 정도가 1부터 100 사이의숫자로 주어진다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스번호를 의미하며 1부터 시작한다)를 출력하고,
각 테스트 케이스마다 100일 중에서 가장 덩어리가 많을 때의 덩어리 개수를 출력하라.

구조화

"X번째날에는 맛있는 정도가 X인 칸을 먹어버린다."고 하여

0부터 입력받은 최고값까지 for문을 돌리고,

해당 값보다 큰 경우만 bfs돌게끔 하여 치즈덩어리 개수 파악

소스 코드

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

public class Solution {

	static int T, N;
	static int[][] cheeze;
	static boolean[][] visited;
	// 상하좌우
	static int[][] way = {{-1,0},{1,0},{0,-1},{0,1}};
	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		
		for (int t = 1; t <= T; t++) 
		{
			int max = Integer.MIN_VALUE;
			int cnt = 0;
			int result = 0;
			N = Integer.parseInt(br.readLine());
			
			cheeze = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) 
			{
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < N; j++) 
				{
					cheeze[i][j] = Integer.parseInt(st.nextToken());
					max = Math.max(max, cheeze[i][j]);
				}
			}
			
			for (int i = 0; i <= max; i++) 
			{
				cnt = 0;
				visited = new boolean[N][N];
				for (int r = 0; r < N; r++) 
				{
					for (int c = 0; c < N; c++) 
					{
						if(cheeze[r][c] > i && !visited[r][c])
						{
							bfs(r,c,i);
							cnt++;
						}
					}
				}
				result = Math.max(result, cnt);
			}
			
			System.out.printf("#%d %d%n",t,result);
		}
	}
	
	private static void bfs(int r, int c, int num) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] { r, c });

		while (!q.isEmpty()) {
			int[] cur = q.poll();
			int cr = cur[0];
			int cc = cur[1];
			visited[r][c] = true;
			
			for (int i = 0; i < 4; i++) {
				int nr = cr + way[i][0];
				int nc = cc + way[i][1];

				if (nr >= 0 && nc >= 0 && nr < N && nc < N) {
					if (!visited[nr][nc] && cheeze[nr][nc] > num) {
						q.add(new int[] { nr, nc });
						visited[nr][nc] = true;
					}
				}

			}

		}
		
	}

}