1743_음식물피하기

사용 알고리즘: bfs

사용 언어: java

 

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

public class Main_bj_1743_음식물피하기 {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] map = new int[n][m];
        for (int i = 0; i < k; i++) {
            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken()) - 1;
            int c = Integer.parseInt(st.nextToken()) - 1;
            map[r][c] = 1; //음식물이 있으면 1
        }
        //입력 끝
        int maxArea = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //음식물이 있으면 갯수 세러 가기
                if(map[i][j] == 1) {
                    Point curPoint = new Point(i, j);
                    maxArea = bfs(curPoint, map, maxArea, n,m);
                }
            }
        }
        System.out.println(maxArea);
    }

    private static int bfs(Point startPoint, int[][] map, int maxArea, int n, int m) {
        int curArea = 1;
        Queue<Point> q = new ArrayDeque<>();
        q.offer(startPoint);
        map[startPoint.x][startPoint.y] = -1; //방문 처리
        
        while (!q.isEmpty()) {
            Point curPoint = q.poll();
            for (int d = 0; d < 4; d++) {
                int nx = curPoint.x + dx[d];
                int ny = curPoint.y + dy[d];

                if(nx>=0 && nx<n && ny>=0 && ny<m && map[nx][ny] == 1) {
                    q.offer(new Point(nx, ny));
                    curArea++;
                    map[nx][ny] = -1;
                }
            }
        }
        
        return Math.max(maxArea, curArea);
    }
}

 

 

덩어리 찾기 -> bfs