[ SWEA / 자바 ] 7733번 치즈도둑

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

SW Expert Academy

---

---

📑 문제

 

N*N 크기의 치즈가 있다.

치즈의 각각 칸(1*1)에는 얼마나 맛있는지 숫자로 작성되어 있다.

N일차에 맛이 N인 치즈를 먹는다.

N일차에 맛이 N인 치즈를 먹은 후, 먹지 않은 치즈들이 몇 덩어리인지 알아내서 치즈 덩어리가 가장 많을 때의 덩어리 개수를 출력한다.

 

💡 입력

✔ 첫 번째 줄에 테스트 케이스의 수 T

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

✔ N개의줄에 걸쳐서 각 칸의 맛있는 정도가 1부터 100 사이의숫자로 제시

 

 

---

---

✨ 풀이과정

✔ 오늘 먹어야 할 치즈 or 이전에 먹은 치즈면 이미 먹은 치즈라고 check

✔ 나머지 부분에 대해 dfs 로 그 치즈 덩어리 크기만큼 check 하는 과정을 반복하며 덩어리 하나가 완전히 check 될때마다 cnt를 추가해준다

✔ 이전 덩어리 개수의 최대값과 지금 치즈의 덩어리 개수를 비교해서 더 큰값을 cheese 값으로 갱신

 

✔ 배열 크기를 N+2, 추가한 테두리를 벽으로 설정한다.

        ✔ 나중에 조건문으로 범위 체크 하는 작업을 하지 않아도 된다

 

✔ 주어진 날짜 중 제일 마지막 날짜를 따로 구하고, 변수에 저장해서 그 날짜까지만 돈다 (이렇게 하면 굳이 100일까지 갈 필요 없다)

 

✔ 치즈 덩어리 개수는 ****무조건 1개이상이므로 1로 초기화 한다

        ✔ 각각의 치즈가 가진 덩어리 개수를 세는 카운트 변수는 초기화를 0으로 해준다

 

 

---

---

📑 코드

import java.util.Scanner;

public class D4_7733_치즈도둑 {
	static int N; // 치즈의 한 변의 길이
	static int[][] dayCheese; // X day - 요정이 치즈 언제 먹는지
	// 델타
	static int[] di;
	static int[] dj;

	static int maxDay; // 마지막에 먹는 날(맛있는 정도가 최대인 날)
	static int cheese; // 치즈 덩어리 판별
	static int cnt; // 몇 덩어리있는지

	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(); // 치즈 한 변의 길이
			dayCheese = new int[N + 2][N + 2]; // 나중에 범위 지정하기 싫으니까 +2 크기로 만들기
			maxDay = 0;

			for (int i = 0; i < N + 2; i++) {
				for (int j = 0; j < N + 2; j++) {
					if (i == 0 || i == N + 1 || j == 0 || j == N + 1) {
						dayCheese[i][j] = 0;
					} else {
						dayCheese[i][j] = sc.nextInt();

						maxDay = Math.max(maxDay, dayCheese[i][j]);
					}
				}
			}

			// 상하좌우 델타
			di = new int[] { -1, 1, 0, 0 };
			dj = new int[] { 0, 0, -1, 1 };

			int cheese = 1; // 제일 많은 치즈 덩어리
			for (int day = 1; day <= maxDay; day++) { // 주어진 날짜만큼 돌자

				boolean[][] eat = new boolean[N + 2][N + 2];
				for (int i = 0; i < N + 2; i++) {
					for (int j = 0; j < N + 2; j++) {
						if (i == 0 || i == N + 1 || j == 0 || j == N + 1) {
							eat[i][j] = true; // 벽을 만들었다
						}
					}
				}

				int cnt = 0; // 이 치즈가 가지고 있는 덩어리

				for (int i = 1; i <= N; i++) {
					for (int j = 1; j <= N; j++) {
						if (dayCheese[i][j] <= day) {

							eat[i][j] = true; // 먹은 & 오늘 먹어야 할 치즈면

						}
					}
				}

				for (int i = 1; i <= N; i++) {
					for (int j = 1; j <= N; j++) {
						if (!eat[i][j]) {// 오늘 날짜에 먹을 치즈가 아니고 이전에도 먹지 않았으면
							cnt++; // 덩어리로 추가해주고

							eat[i][j] = true;
							dfs(i, j, eat); // dayCheese[i][j]와 이어진 치즈 탐색
						}
					}
				}
				cheese = Math.max(cheese, cnt); // 각 날짜의 치즈덩어리 개수와 이전의 최대 치즈 덩어리 개수를 비교
			}

			System.out.println("#" + tc + " " + cheese);

		} // testcase
	} // main

	private static void dfs(int i, int j, boolean[][] eat) {

		for (int d = 0; d < 4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];

			if (eat[ni][nj]) {
				continue;
			} else {
				eat[ni][nj] = true;
				dfs(ni, nj, eat);
			}
		}

	}

}

---

---