[SWEA] 7733 치즈도둑

AngJ·2026년 9월 29일

BFS SWEA 알고리즘

코딩테스트

목록 보기

16/22

문제

SWEA_7733_치즈도둑

요약

정사각형의 치즈가 인풋으로 주어지고, 각 칸마다 숫자가 있다.
각 시간마다 시간과 일치하는 숫자의 칸을 먹는다.
그 과정에서 남은 치즈들의 덩어리가 생기는데, 전체 치즈를 다 먹는 과정에서 생기는 치즈 덩어리의 최댓값을 구해라!

접근

이 문제를 보자마자 '격자 그래프'가 떠올랐다.
그리고, 덩어리들을 묶어야하니까 BFS로 찾는 방식을 택했다.
BFS로 아직 남아있는 덩어리들을 방문처리를 하고, 다 방문했으면 덩어리 개수를 1 올리는 방식!

알고리즘

맛있는 정도의 최댓값을 인풋을 받을 때, 저장한다
맛있는 정도가 최댓값이 될 때까지 아래의 과정을 반복한다.
격자 그래프를 순회하면서 지금의 맛있는 정도보다 높은 칸이면서 아직 방문하지 않은 칸을 찾는다.
3-1. BFS 탐색
3-1-1. 처음 들어온 칸을 Queue에 넣는다.
3-1-2. 해당 칸을 방문처리한다.
3-1-3. Queue가 비어있지 않을때까지 반복한다.
3-1-4. Queue의 요소를 뺀다.
3-1-5. 해당 요소의 위치를 방문처리한다.
3-1-6. 4방처리하면서 아직 방문하지 않았으면서, 지금의 맛있는 정도보다 높은 칸이면 해당 칸을 Queue에 넣는다.
3-2. 덩어리의 개수를 1 증가시킨다.
지금까지의 덩어리 수와 지금 맛있는 정도의 덩어리 수의 최댓값을 비교 후 최댓값 업데이트

제출 코드

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

public class swea_7733_치즈도둑 {
    static int[][] cheese;
    static boolean[][] visited;
    static int res;
    static int N;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine()); // 치즈 배열 크기

        for (int tc = 1; tc <= T; tc++) {
            N = Integer.parseInt(br.readLine());
            cheese = new int[N][N]; // 치즈 원본 생성
            int X = 0;
            res = 1;
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine(), " ");
                for (int j = 0; j < N; j++) {
                    cheese[i][j] = Integer.parseInt(st.nextToken());
                    if (cheese[i][j] > X) X = cheese[i][j];
                }
            }

            int cnt = 1;

            while (cnt <= X) {
                visited = new boolean[N][N];
                int combine = 0;
                for (int r = 0; r < N; r++) {
                    for (int c = 0; c < N; c++) {
                        if (cheese[r][c] > cnt && !visited[r][c]) {
                            // System.out.println("cheese[r][c] <= cnt && !visited[r][c]");
                            Node n = new Node(r, c);
                            bfs(n, cnt); // bfs돌리면서 visited 처리하고 다 돌면 카운트처리
                            combine++;
                        }
                    }
                }
                // 치즈덩어리 개수 비교
                if (res < combine) {
                    res = combine;
                    // System.out.println("res < combine");
                }
                cnt++;
            }
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        } // end of tc
        System.out.println(sb.toString());
    } // end of main

    public static class Node {
        int x;
        int y;

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

    static void bfs(Node n, int cnt) {
        // 방문을 기록할 노트
        Queue<Node> q = new ArrayDeque<>();
        // 시작 노드 집어 넣는다.
        q.offer(n);
        int r = n.x;
        int c = n.y;
        // 시작노드 방문처리
        visited[r][c] = true;

        while(!q.isEmpty()) {
            Node next = q.poll();
            for (int i = 0; i < 4; i++) {
                int nr = next.x+dr[i];
                int nc = next.y+dc[i];
                // 범위 가두기
                if (nr >= 0 && nr < N && nc >= 0 && nc < N && cheese[nr][nc] > cnt && !visited[nr][nc]) {
                    q.offer(new Node(nr, nc));
                    visited[nr][nc] = true;
                }
            }
        }
    }
} // end of class