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

https://www.acmicpc.net/problem/1743

이 문제는 dfs를 이용하여 푸는 문제이다. 음식물 쓰레기가 있다고 가정한 후, 상하좌우를 비교하여 연속된 곳에 있으면 그 곳을 찾으면 된다.
즉, 주어진 2차원 배열에서 음식물 쓰레기가 있는 위치를 기준으로 dfs를 수행하며, 인접한 음식물 쓰레기의 개수를 세는 방식인 것이다. 배열을 순회하며 음식물 쓰레기가 있으면 dfs를 호출하고, 상하좌우의 인접한 위치를 탐색하면서 아직 방문하지 않은 음식물 쓰레기가 있는 경우 dfs를 또 호출하여 깊이를 탐색하는 것이다.

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

public class Main {
    public static boolean[][] visited;
    public static int[][] arr;
    public static int N, M, K, answer, max;
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        //방문한 적이 없고 쓰레기라면 dfs 탐색
        //가장 큰 음식물 쓰레기의 개수를 구하는 거니까 인접한 경우(위, 아래가 붙은 경우) 1씩 더해주면 됨
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input1 = br.readLine().split(" ");
        N = Integer.parseInt(input1[0]); //통로의 세로 길이
        M = Integer.parseInt(input1[1]); //통로의 가로 길이
        K = Integer.parseInt(input1[2]); //떨어진 음식물 쓰레기의 개수
        arr = new int[N][M]; //세로 가로
        visited = new boolean[N][M];
        for (int i = 0; i < K; i++) { //음식물 쓰레기가 있는 곳을 입력
            String[] input = br.readLine().split(" ");
            int r = Integer.parseInt(input[0]); //위에서부터(세로)
            int c = Integer.parseInt(input[1]); //왼쪽에서부터(가로)
            arr[r - 1][c - 1] = 1;
        }
        max = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (arr[i][j] == 1 && !visited[i][j]) { //쓰레기이고 방문하지 않은 경우에만 탐색
                    answer = 0;
                    dfs(i, j);
                    if (answer > max) {
                        max = answer;
                    }
                }
            }
        }
        System.out.println(max);
        br.close();
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;
        answer++;

        for (int i = 0; i < 4; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < N && nowY < M) {
                if (!visited[nowX][nowY] && arr[nowX][nowY] == 1) {
                    dfs(nowX, nowY);
                }
            }
        }
    }
}