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

문제

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

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

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

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

 

 

입력

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

좌표 (r, c)의 r은 위에서부터, c는 왼쪽에서부터가 기준이다.

 

 

출력

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

 

 

예제

 

코드

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_BJ_1743_ {
    
    static class info{
        int x, y;
 
        public info(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int N,M,K, ans;
    static int [][] map;
    static boolean [][] visited;
    static int [] dx = {-1,0,1,0};
    static int [] dy = {0,1,0,-1};
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine()," ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        map = new int[N][M];
        visited = new boolean[N][M];
        
        for(int i=0;i<K;i++) {
            st = new StringTokenizer(br.readLine()," ");
            map[Integer.parseInt(st.nextToken())-1][Integer.parseInt(st.nextToken())-1]=1;
        }
        
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) {
                if(map[i][j]==1 && !visited[i][j]) bfs(i,j);
            }
        }
        System.out.println(ans);
 
    }
    
    public static void bfs(int x, int y) {
        Queue<info> queue = new LinkedList<>();
        queue.offer(new info(x,y));
        visited[x][y]=true;
        
        int count=1;
        while(!queue.isEmpty()) {
            info temp = queue.poll();
            
            for(int i=0;i<4;i++) {
                int nx = temp.x+dx[i];
                int ny = temp.y+dy[i];
                
                if(range(nx,ny) && !visited[nx][ny] && map[nx][ny]==1) {
                    visited[nx][ny]=true;
                    queue.offer(new info(nx,ny));
                    count++;
                }
            }
            ans = Math.max(ans, count);
        }
        
    }
    public static boolean range(int x, int y) {
        return x>=0 && y>=0 && x<N && y<M;
    }
}