[SWEA/Java] 7733. 치즈 도둑

[SWEA/Java] 7733. 치즈 도둑

SW Expert Academy

---

문제 해석

이 문제에서는 N x N 크기의 치즈 판이 주어지며, 각 칸에는 치즈의 나이가 표시된다. 치즈는 매일 일정 수의 날이 지나면 녹는다. 문제의 목표는 모든 치즈가 녹기 전에 가장 많은 연결된 치즈 덩어리의 개수를 구하는 것이다.

풀이 과정

• io 메소드는 여러 테스트 케이스에 대해 입력을 받고, 각 테스트 케이스에 대해 sol 메소드를 호출한다.
• sol 메소드는 1일부터 최대 치즈 나이(day)까지 각 날짜에 대해 치즈가 녹는 상황을 시뮬레이션하고, 그날의 연결된 치즈 덩어리 수를 계산한다.
• eat 메소드는 특정 날짜에 해당하는 치즈를 모두 녹인다.
• bfs 메소드는 BFS를 사용하여 연결된 치즈 덩어리의 크기를 계산한다.

코드

package edu.ssafy.im.SWEA.D4.No7733;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
    private int[][] graph; // 치즈 판
    private int ans, day; // 최대 연결된 치즈 덩어리 수, 최대 날짜
    private final static int[][] direction = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}}; // 이동 방향 (상하좌우)
    private boolean[][] visited; // 방문 여부

    public static void main(String[] args) throws IOException {
        new Solution().io();
    }

    private void io() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        int testCase = Integer.parseInt(br.readLine()); // 테스트 케이스 수
        for (int t = 1; t <= testCase; t++) {
            int n = Integer.parseInt(br.readLine()); // 치즈 판의 크기
            graph = new int[n][n];
            day = 0; // 최대 치즈 나이 초기화
            for (int i = 0; i < n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    graph[i][j] = Integer.parseInt(st.nextToken());
                    if (graph[i][j] > day) day = graph[i][j]; // 최대 치즈 나이 계산
                }
            }
            ans = 1; // 최소 한 덩어리는 존재
            sol(); // 솔루션 실행
            sb.append("#").append(t).append(" ").append(ans).append("\n"); // 결과 추가
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private void sol() {
        for (int d = 1; d <= day; d++) {
            eat(d); // 치즈 녹이기

            int res = 0; // 연결된 치즈 덩어리 수
            visited = new boolean[graph.length][graph.length];
            for (int i = 0; i < graph.length; i++) {
                for (int j = 0; j < graph.length; j++) {
                    if (graph[i][j] != 0 && !visited[i][j]) {
                        bfs(i, j); // 연결된 치즈 덩어리 탐색
                        res++;
                    }
                }
            }
            ans = Math.max(ans, res); // 최대값 갱신
        }
    }

    private void bfs(int x, int y) {
        Queue<Point> queue = new ArrayDeque<>();
        queue.offer(new Point(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            Point p = queue.poll();
            for (int d = 0; d < direction.length; d++) {
                int nx = p.x + direction[d][0];
                int ny = p.y + direction[d][1];

                if (checkStatus(nx, ny)) {
                    visited[nx][ny] = true;
                    queue.offer(new Point(nx, ny));
                }
            }
        }
    }

    private boolean checkStatus(int nx, int ny) {
        return 0 <= nx && nx < graph.length && 0 <= ny && ny < graph.length && !visited[nx][ny] && graph[nx][ny] != 0;
    }

    private void eat(int d) {
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if (graph[i][j] == d) {
                    graph[i][j] = 0; // 치즈 녹임
                }
            }
        }
    }

    class Point {
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N2×D)이다. 여기서 N은 그리드의 크기, D는 최대 치즈 나이다. 매 일마다 모든 치즈 칸에 대해 연결된 치즈 덩어리를 탐색하기 때문이다.

느낀점

이 문제는 각 날짜에 따른 동적인 그리드 상태 변화를 추적하고, 변화된 상태에서 연결된 구성 요소의 크기를 계산하는 문제였다. BFS를 사용하여 효율적으로 구성 요소의 크기를 계산할 수 있었다. 다양한 상황에서 그래프 탐색 기법을 활용하는 능력이 중요하다는 것을 깨달았다.