[JAVA/1743번] 음식물 피하기

문제

입력 및 출력

풀이

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

class Main {
    public static int N;
    public static int M;
    public static int K;
    public static int[][] map;
    public static boolean[][] visited;
    public static int[] dx = {0, 0, -1, 1};
    public static int[] dy = {1,-1,  0, 0};
    public static int count;
    public static int result = Integer.MIN_VALUE;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");

        // N, M, K(세로, 가로, 음식물 쓰레기의 개수)
        N = Integer.parseInt(temp[0]);
        M = Integer.parseInt(temp[1]);
        K = Integer.parseInt(temp[2]);

        // 지도 데이터, 방문여부
        map = new int[N + 1][M + 1];
        visited = new boolean[N + 1][M + 1];

        for (int i = 0; i < K; i++) {
            String[] temp2 = br.readLine().split(" ");
            int one = Integer.parseInt(temp2[0]);
            int two = Integer.parseInt(temp2[1]);
            map[one][two] = 1;
        }

        // BFS메소드 호출
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    // 음식물의 크기는 한개일 경우에 1이기 때문에
                    count = 1;

                    // BFS메소드 호출
                    BFS(i, j);

                    // 최대크기의 음식물 result에 저장
                    if (result < count) {
                        result = count;
                    }
                }
            }
        }

        // 결과 값 출력
        System.out.println(result);
    }
    public static void BFS(int x, int y) {
        Queue < Node > queue = new LinkedList < > ();

        queue.add(new Node(x, y));
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            // 큐의 가장 앞에 있는 원소를 추출
            Node node = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];

                if (isRange(nx, ny)) {
                    if (map[nx][ny] == 1 && !visited[nx][ny]) {
                        queue.add(new Node(nx, ny));
                        visited[nx][ny] = true;
                        count++;
                    }
                }
            }
        }
    }
    public static boolean isRange(int x, int y) {
        if (x > 0 && y > 0 && x <= N && y <= M) {
            return true;
        }
        return false;
    }
}

class Node {
    // x축, y축
    int x, y;

    // Node생성자
    public Node(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법
바로 직전에 해결했던 단지번호붙이기와 유사한 문제였다. 단지번호붙이기 문제는 붙어있는 집을 단지로 규정하고, 단지의 개수와 단지 내 집의 개수를 구하는 문제였다면 이번 문제는 음식물 중 가장 큰 음식물을 출력만하면 되는 간단한 문제였다.

음식물이 상, 하, 좌, 우에 붙어있을 경우 크기가 커짐으로 전체적인 동작 방식은 이전 문제와 동일하고 다른 점은 최댓값을 계속 갱신해서 크기가 가장 큰 음식물을 화면에 출력해준 점이 달랐다.