[BOJ] 음식물 피하기

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다.

이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다.

통로에 떨어진 음식물을 피해가기란 쉬운 일이 아니다. 따라서 선생님은 떨어진 음식물 중에 제일 큰 음식물만은 피해 가려고 한다.

선생님을 도와 제일 큰 음식물의 크기를 구해서 “10ra"를 외치지 않게 도와주자.

풀이

전형적인 BFS 문제이다.
음식물의 위치를 "#"으로 표시해두었고, 정상적인 길은 null 타입이 들어가도록 하였다.
따라서 탐색중 null이 아니면 음식물이 존재한다는 뜻 이므로 깊이 탐색을 진행하여 가장 큰 갯수를 세어준다.

class Main {
    static int[] x_loc = {1, -1, 0, 0};
    static int[] y_loc = {0, 0, 1, -1};
    static int N;
    static int M;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        int K = Integer.parseInt(str[2]);
        String[][] map = new String[N][M];
        boolean[][] visited = new boolean[N][M];

        for(int i = 0; i < K; i++) {
            str = br.readLine().split(" ");
            map[Integer.parseInt(str[0]) - 1][Integer.parseInt(str[1]) - 1] = "#";
        }

        int answer = 0;

        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if (map[i][j] != null && !visited[i][j]) {
                    int count = bfs(i, j, visited, map);
                    answer = Math.max(answer, count);
                }
            }
        }

        System.out.println(answer);


    }

    static int bfs(int a, int b, boolean[][] visited, String[][] map) {
        int count = 0;
        Queue<Loc> queue = new LinkedList<>();
        queue.add(new Loc(a, b));
        visited[a][b] = true;

        while(!queue.isEmpty()) {
            Loc loc = queue.poll();
            count++;
            for(int i = 0; i < 4; i++) {
                int x = loc.x + x_loc[i];
                int y = loc.y + y_loc[i];
                if (check(x, y, visited) && map[x][y] != null) {
                    visited[x][y] = true;
                    queue.add(new Loc(x, y));
                }
            }
        }

        return count;
    }

    static boolean check(int x, int y, boolean[][] visited) {
        return (x >= 0 && x < N) && (y >= 0 && y < M) && !visited[x][y];
    }

    static class Loc {
        int x;
        int y;

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

https://github.com/Win-9/Algorism/tree/main/BOJ/%EC%9D%8C%EC%8B%9D%EB%AC%BC%20%ED%94%BC%ED%95%98%EA%B8%B0