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

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

 

그래프 탐색 문제

 

인접한 '#'끼리 붙여 도형을 만들었을 때, 넓이가 가장 큰 것(의 넓이) 출력

 

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

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int ans = 0;
    int R = Integer.parseInt(st.nextToken());
    int C = Integer.parseInt(st.nextToken());
    int K = Integer.parseInt(st.nextToken());

    boolean[][] m = new boolean[R][C];
    boolean[][] vst = new boolean[R][C];

    int[] dr = {0, 0, -1, 1};
    int[] dc = {-1, 1, 0, 0};

    for (int i = 0; i < K; i++) {
      st = new StringTokenizer(br.readLine());
      m[Integer.parseInt(st.nextToken()) - 1][Integer.parseInt(st.nextToken()) - 1] = true;
    }

    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {

        if (!vst[i][j] && m[i][j]) {

          int sum = 1;

          Queue<int[]> q = new ArrayDeque<>();
          vst[i][j] = true;
          q.offer(new int[]{i, j});

          while (!q.isEmpty()) {
            int[] cur = q.poll();
            int r = cur[0];
            int c = cur[1];

            for (int k = 0; k < 4; k++) {
              int tr = r + dr[k];
              int tc = c + dc[k];

              if (tr >= 0 && tr < R && tc >= 0 && tc < C && !vst[tr][tc] && m[tr][tc]) {

                vst[tr][tc] = true;
                sum++;
                q.offer(new int[]{tr, tc});
              }
            }
          }

          ans = Math.max(sum, ans);
        }
      }
    }
    System.out.println(ans);
  }
}