[BOJ/Java] 음식물 피하기 (1713)

음식물 피하기 (1713)

1. 문제 분석

문제 개요

• N x M 크기의 격자판에 K개의 음식물 쓰레기가 흩어져 있습니다.
• 각 음식물 쓰레기는 인접한 칸(상, 하, 좌, 우)으로 연결될 수 있으며, 연결된 음식물 쓰레기 덩어리 중 가장 큰 크기를 구하는 문제입니다.

입력 형식

• 첫 번째 줄에 격자의 크기 N, M과 음식물 쓰레기의 수 K가 주어집니다.
• 이후 K개의 줄에 음식물 쓰레기가 위치한 좌표 (r, c)가 주어집니다.

출력 형식

• 연결된 음식물 쓰레기 중 가장 큰 덩어리의 크기를 출력합니다.

2. 알고리즘 종류

이 문제는 BFS(너비 우선 탐색) 알고리즘을 사용하여 연결된 음식물 쓰레기의 크기를 구하는 문제입니다. BFS를 통해 각 쓰레기 덩어리의 크기를 구하고, 그중 최대 크기를 찾는 방식으로 해결합니다.

3. 주요 부분 및 코드 작성 방법

1. BFS 사용

• BFS를 사용하여 각 음식물 쓰레기의 덩어리 크기를 계산합니다.
• 방문하지 않은 음식물 쓰레기 위치에서 BFS를 시작해 연결된 모든 쓰레기를 탐색하고 크기를 셉니다.

2. 최대 크기 업데이트

• 각 BFS 탐색 후, 계산된 덩어리 크기를 갱신하며 최종적으로 가장 큰 크기를 찾습니다.

4. 코드 설명

(1) 메인 함수 (main)

• 입력 처리

    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());  // 음식물 쓰레기의 개수

  • 첫 번째 줄에서 격자의 크기(N, M)와 음식물 쓰레기의 수(K)를 입력받아 각각의 변수에 저장합니다.

• 초기화 및 입력된 위치 저장

    food = new int[N][M];  // 음식물 쓰레기 위치를 저장하는 2차원 배열
    visited = new boolean[N][M];  // 방문 여부를 체크하는 2차원 배열
  
    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;  // 입력된 열 좌표
  
        food[r][c] = 1;  // 해당 위치에 음식물 쓰레기 표시
    }

  • food 배열은 음식물 쓰레기의 위치를 저장하며, visited 배열은 해당 위치를 방문했는지 확인합니다.
  • K개의 음식물 쓰레기의 위치를 입력받아 food 배열에 표시합니다.

• BFS를 통한 덩어리 탐색

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            if(food[i][j] == 1 && !visited[i][j]) bfs(i, j);
        }
    }

  • 모든 격자 칸을 순회하며, 음식물 쓰레기가 있고 방문하지 않은 위치를 찾으면 BFS를 시작하여 연결된 덩어리의 크기를 계산합니다.

• 결과 출력

    System.out.println(result);  // 가장 큰 덩어리의 크기를 출력

  • BFS를 통해 계산된 가장 큰 음식물 쓰레기 덩어리의 크기를 출력합니다.

(2) BFS 함수 (bfs)

• 초기화

    Queue<Point> q = new LinkedList<>();
    visited[x][y] = true;  // 시작점을 방문 처리
    q.offer(new Point(x, y));  // 큐에 시작점 추가
  
    int cnt = 1;  // 현재 덩어리 크기 초기화

  • BFS 탐색을 위한 큐를 초기화하고, 시작점을 방문 처리한 후 큐에 넣습니다.
  • 덩어리 크기를 나타내는 cnt 변수를 1로 초기화합니다.

• BFS 탐색

    while(!q.isEmpty()) {
        Point p = q.poll();  // 큐에서 점을 꺼냄
        for(int i = 0; i < 4; i++) {  // 4방향 탐색
            int nx = p.x + dx[i];  // 다음 탐색할 행 위치
            int ny = p.y + dy[i];  // 다음 탐색할 열 위치
  
            if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny] || food[nx][ny] != 1) continue;
  
            q.add(new Point(nx, ny));  // 큐에 추가
            visited[nx][ny] = true;  // 방문 처리
            cnt++;  // 덩어리 크기 증가
        }
    }
    result = Math.max(result, cnt);  // 최대 덩어리 크기 업데이트

  • 큐가 빌 때까지 인접한 칸들을 탐색하여, 범위 내에 있고 방문하지 않았으며 음식물이 있는 경우 큐에 추가하고, 덩어리 크기를 증가시킵니다.
  • 탐색이 끝나면 result 변수에 최대 덩어리 크기를 업데이트합니다.

5. 전체 코드

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

public class Main {
    static int N, M, K; // N: 행, M: 열, K: 음식물 쓰레기 개수
    static boolean[][] visited; // 방문 여부를 체크하는 배열
    static int[][] food; // 음식물 쓰레기 위치를 나타내는 배열
    static int result; // 최대 음식물 쓰레기 덩어리 크기

    // 상, 우, 하, 좌 방향을 나타내는 배열
    static int[] dx = new int[] {-1, 0, 1, 0};
    static int[] dy = new int[] {0, 1, 0, -1};

    // 좌표를 나타내는 클래스
    static class Point {
        int x, y; // x: 행, y: 열
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 입력받은 N, M, K 값을 초기화
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        // 음식물 쓰레기 위치와 방문 여부를 저장하는 배열 초기화
        food = new int[N][M];
        visited = new boolean[N][M];

        // K개의 음식물 쓰레기 위치를 입력받아 배열에 저장
        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; // 입력받은 열 좌표

            food[r][c] = 1; // 해당 위치에 음식물 쓰레기 표시
        }

        // 음식물 쓰레기 위치를 탐색하여 연결된 덩어리 크기 계산
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                if(food[i][j] == 1 && !visited[i][j]) bfs(i, j);
            }
        }

        // 결과 출력
        System.out.println(result);
    }

    // BFS 함수: 주어진 위치에서 시작해 연결된 음식물 쓰레기의 크기를 계산
    static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        visited[x][y] = true; // 시작점을 방문 처리
        q.offer(new Point(x, y)); // 큐에 시작점 추가

        int cnt = 1; // 현재 덩어리 크기 초기화

        while(!q.isEmpty()) {
            Point p = q.poll(); // 큐에서 점을 꺼냄
            for(int i = 0; i < 4; i++) { // 4방향 탐색
                int nx = p.x + dx[i]; // 다음 탐색할 행 위치
                int ny = p.y + dy[i]; // 다음 탐색할 열 위치

                // 범위를 벗어나거나, 이미 방문했거나, 음식물 쓰레기가 없는 경우 스킵
                if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny] || food[nx][ny] != 1) continue;

                q.add(new Point(nx, ny)); // 큐에 추가
                visited[nx][ny] = true; // 방문 처리
                cnt++; // 덩어리 크기 증가
            }
        }
        result = Math.max(result, cnt); // 최대 덩어리 크기 업데이트
    }
}