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

문제를 읽는데 순간 당황했다

오랜만에 다시 풀기 시작했기 때문에 웃긴 문제를 풀게 된 걸까 ..

---

1743번: 음식물 피하기
(15)

---

문제 풀이

좌표에 존재하는 그래프 들 중, 가장 큰 크기를 가진 그래프의 크기를 구하는 것과 같다.

그래프는, 좌우위아래로 연속하는 칸들로 이루어져있다.

3 4 5
3 2
2 2
3 1
2 3
1 1
■□□□
□■■□
■■□□

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

public class Main{

    public static int[][] board = new int[100][100];
    public static boolean[][] visit = new boolean[100][100];
    public static int n,m;
    public static int max=0;
    public static int[][] dirs = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};

    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void setting() throws IOException {
        int k = 0;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        int r=0,c=0;
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken())-1;
            c = Integer.parseInt(st.nextToken())-1;
            board[r][c]=1;
        }

    }
    public static void solve(){
        int sum=0;
        for(int r=0;r<n;r++){
            for(int c=0;c<m;c++){
                if(board[r][c]!=0 && visit[r][c]==false){
                    bfs(r,c);
                }

            }
        }
    }
    public static void bfs(int sr,int sc){
        LinkedList<int[]> q = new LinkedList<>();

        visit[sr][sc] = true;
        q.add(new int[]{sr,sc});
        int sum = 1;
        int ny=0,nx=0;
        while(q.isEmpty()==false){
            int[] cur = q.poll();
            for(int dir=0;dir<dirs.length;dir++){
                ny = cur[0]+dirs[dir][0];
                nx = cur[1]+dirs[dir][1];
                if(ny<0||nx<0||ny>=n||nx>=m)continue;
                if(board[ny][nx]==1 && visit[ny][nx]==false){
                    q.add(new int[]{ny,nx});
                    visit[ny][nx]=true;
                    sum++;
                }
            }
        }
        if(sum>max)max=sum;
    }
    
    public static void main(String[] args)throws IOException {
        setting();
        solve();
        System.out.println(max);

    }

}