[알고리즘 문제 풀이] 백준 1743번 음식물 피하기 (BFS/DFS)

//import java.util.*;
//import java.io.*;
import java.awt.Point;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main{

    static String[][] arr;
    static boolean[][] visited;

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



    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());
        // 음식물 쓰레기의 개수
        k = Integer.parseInt(st.nextToken());


        arr=new String[n][m]; // [세로][가로]
        visited= new boolean[n][m];

        for(int j=0;j<n;j++){
            for(int s=0;s<m;s++){
                arr[j][s]=".";
            }
        }

        for(int i=0;i<k;i++){
            String[] line = br.readLine().split(" ");
            int r = Integer.parseInt(line[0]);
            int c = Integer.parseInt(line[1]);

            /* 아래와 같이 사용하면 NumberFormat 에러 발생함.
            왜냐하면,만약 숫자가 두 자리 숫자이거나 공백이 여러 개 있을 경우,
             line.substring(2)가 정확히 숫자를 가져오지 못할 수 음.
             예를 들어 "10 11"이라는 입력이 있을 때 line.substring(2)는 "0 11"를 반환함.
             이는 숫자가 아니므로 NumberFormatException을 발생시킴.
            String line = br.readLine();
            int r = Integer.parseInt(line.substring(0,1));
            int c = Integer.parseInt(line.substring(2));*/
            arr[r-1][c-1]="#";

        }

        max = 0;
        count =0;

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){

                if(visited[i][j] == true || arr[i][j].equals(".")==true ){
                    continue;
                }
                else{
                    dfs(i,j);
                    if(count > max){
                        max = count;
                    }

                }
                count=0;
            }
        }

        System.out.println(max);
    }

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

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


            if(nextX<0 || nextX>=n || nextY<0 || nextY>=m) continue;
            if(visited[nextX][nextY]) continue;
            if(arr[nextX][nextY].equals(".")) continue;


            dfs(nextX,nextY);

    }
}

}