백준 17025 (Icy Perimeter) - java

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

17025번: Icy Perimeter

문제 

Each '.' character represents empty space and each '#' character represents a 1×1$1 \times 1$ square cell of ice cream.

Unfortunately, the machine isn't working very well at the moment and might produce multiple disconnected blobs of ice cream (the figure above has two). A blob of ice cream is connected if you can reach any ice cream cell from every other ice cream cell in the blob by repeatedly stepping to adjacent ice cream cells in the north, south, east, and west directions.

Farmer John would like to find the area and perimeter of the blob of ice cream having the largest area. The area of a blob is just the number of '#' characters that are part of the blob. If multiple blobs tie for the largest area, he wants to know the smallest perimeter among them. In the figure above, the smaller blob has area 2 and perimeter 6, and the larger blob has area 13 and perimeter 22.

Note that a blob could have a "hole" in the middle of it (empty space surrounded by ice cream). If so, the boundary with the hole also counts towards the perimeter of the blob. Blobs can also appear nested within other blobs, in which case they are treated as separate blobs.

 

접근

• 분리된 두 영역에 대하여 가장 큰 영역의 크기와 둘레를 구하는 문제이다.
  • 영역의 크기는 #의 개수
  • 둘레는 변의 개수를 의미한다.

유형 : BFS

• 둘레를 구하는 방법은 간단한데 #인 지점을 기준으로 주변의 .인 땅과 영역 범위 바깥의 땅의 개수를 구하면 된다. 하지만 주의해야 할 점은 중복이 가능하다는 것이다. 둘레를 구하는 경우 방문처리는 하지 않아도 된다.

전체 코드

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

public class Main {
    static int n = 0;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    static int max  = 0;
    static int per = 0;

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

        n = Integer.parseInt(st.nextToken());
        char[][] board = new char[n+1][n+1];

        for(int i=1;i<=n;i++){
            String line = br.readLine();
            for(int j=1;j<=n;j++){
                board[i][j] = line.charAt(j-1);
            }
        }

        boolean[][] visit = new boolean[n+1][n+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(board[i][j] == '#' && !visit[i][j]){
                    visit[i][j] = true;
                    bfs(i,j,visit,board);
                }
            }
        }

        System.out.println(max+" "+per);
        br.close();
    }

    static void bfs(int x,int y,boolean[][] visit,char[][] board){
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(x,y));

        int count = 1;
        int p = 0;

        while(!q.isEmpty()){
            Node cur = q.poll();

            for(int i=0;i<4;i++){
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];

                if(nx < 1 || nx > n || ny < 1 || ny > n) {
                    p = p + 1;
                    continue;
                }

                if(board[nx][ny] == '.'){
                    p = p + 1;
                }

                if(visit[nx][ny])
                    continue;

                if(board[nx][ny] == '#'){
                    visit[nx][ny] = true;
                    count = count + 1;
                    q.add(new Node(nx,ny));
                }
            }
        }

        if(max < count){
            max = count;
            per = p;
        }

        else if(max == count){
            per = Math.min(per , p);
        }

    }

}

class Node{
    int x;
    int y;

    Node(int x,int y){
        this.x = x;
        this.y = y;
    }
}