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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class bj_1743 {

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int n;
    static int m;
    static int k;

    static int cnt;

    static int[][] graph;

    public static void main(String[] args) throws IOException {
        String s = br.readLine();

        String[] split = s.split(" ");
        n = Integer.parseInt(split[0]);//세로
        m = Integer.parseInt(split[1]);//가로
        k = Integer.parseInt(split[2]);//음쓰 숫자

        graph = new int[n][m];

        for (int i = 0; i < k ; i++){
            String trash = br.readLine();
            String[] trashSplit = trash.split(" ");

            int row = Integer.parseInt(trashSplit[0]);
            int column = Integer.parseInt(trashSplit[1]);
            graph[row-1][column-1] = 1;
        }

        int result =0;
        for (int i = 0; i< n; i++){
            for (int j = 0; j < m; j++){
                if(graph[i][j] == 1){
                    cnt =0;
                    dfs(i, j);
                    result = Math.max(result, cnt);
                }
            }
        }

        System.out.println(result);
    }

    private static void dfs(int x, int y) {
        graph[x][y] = 0;
        cnt++;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < n && ny < m && graph[nx][ny] == 1) {
                dfs(nx, ny);
            }
        }
    }
}

• 따로 방문 여부를 배열로 선언해서 사용하지 않았다.
• 음식물 쓰레기가 있는 곳을 1로 표현해 해당 부분에 처음에 도달하면 마지막 부분까지 cnt를 확인할 수 있게 진행했다.
• 따로 방문 여부를 확인하는 배열을 선언하지 않아 해당 부분을 처음 들어가서 4방향으로 갈수 있는 음쓰 끝부분까지 계속 dfs를 돌리며 해당 graph[x][y] =1 부분을 0으로 만들어주었다.
• 음쓰의 크기를 전과 비교하기 위해서 result라는 변수를 선언해 음쓰 덩어리 부분의 크기를 비교할 수 있게 했다.