[백준] 1743번 음식물 피하기 - 자바

1743번: 음식물 피하기

문제

코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.

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

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

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

입력

첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다.  그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다.

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다. 입력으로 주어지는 좌표는 중복되지 않는다.

 

출력

첫째 줄에 음식물 중 가장 큰 음식물의 크기를 출력하라.

예제 입출력

 

풀이

NxM 통로의 모든 칸을 반복문을 돌면서 DFS로 탐색했다.

이 때, 다음 조건을 만족하는 경우에만 탐색하도록 했다.

1. 해당 칸에 음식물이 있다.
2. 해당 칸을 방문한 적이 없다.

각 칸의 탐색을 마친 후에는 방금 탐색한 음식물의 크기와 지금까지의 최대 크기와 비교하여 최대 크기를 갱신했다.

 

코드

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

public class Main {
    static int N;
    static int M;

    static boolean[][] visited;
    static boolean[][] isDirty;

    // {상, 하, 좌, 우} 방향 전환
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 1};

    // 음식물 사이즈
    static int size;

    public static void main(String[] args) throws IOException {
        // 입력 받기, 각 변수 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        visited = new boolean[N+1][M+1];
        isDirty = new boolean[N+1][M+1];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            isDirty[r][c] = true;
        }

        int answer = 0;

        // 모든 칸을 이동하며 dfs 탐색
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                // 조건: (1) 음식물이 있어야 하고, (2) visited에 없어야 함
                if (isDirty[i][j] && !visited[i][j]) {
                    size = 0;
                    dfs(i, j);

                    // dfs 다 돌고 나서 max size 갱신하기
                    answer = Math.max(answer, size);
                }
            }
        }

        System.out.println(answer);

    }

    public static void dfs(int r, int c) {
        visited[r][c] = true;
        size++;

        // 상, 하, 좌, 우 방향으로 다음 노드 탐색
        for (int i = 0; i < 4; i++) {
            int nr = r + dy[i];
            int nc = c + dx[i];

            if (nr > 0 && nr <= N && nc > 0 && nc <= M && isDirty[nr][nc] && !visited[nr][nc]) {
                dfs(nr, nc);
            }
        }

    }
}