문제 풀이

bfs를 통해서 넓이를 구하고 거기에 더불어 둘레를 구해주는 방식으로 해결하면 된다.
둘레는 bfs 루프의 각 지점에서 cnt = 4로 시작해서 동서남북 각 방향마다 #이 있다면 하나씩 줄여가면서 몇 개의 방향에서 노출되어 있는지 확인하면 된다.

넓이가 최대인 구역과 그 둘레를 구하되, 넓이가 같은 구역이 여러 군데 있다면 그중 둘레가 더 작은 구역을 출력하면 된다.

넓이를 구하는 것과 둘레를 구하는 것을 같이해야지 시간초과가 안 날 수 있는 것 같다.

문제 링크

boj/17025

소스코드

PS/17025.java

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;


public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int []dx = {1,0,0,-1};
    static int []dy = {0,1,-1,0};
    static int n;
    static char [][]arr;
    static Boolean [][]visit;
    static int result;
    static int result2;
    public static class Pair {
        int x,y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        arr = new char[n][n];
        visit = new Boolean[n][n];
        result = -1;
        result2 = 987654321;
        for(int i=0;i<n;i++)
        Arrays.fill(visit[i], false);
        for(int i=0;i<n;i++)
            arr[i] = br.readLine().toCharArray();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
                bfs(j,i);
        }
        bw.write(Integer.toString(result) +" "+ Integer.toString(result2));
        bw.flush();
    }

    static void bfs(int x, int y)
    {
        if (visit[y][x] || arr[y][x] != '#')
            return ;
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(x, y));
        visit[y][x] = true;
        int res = 1;
        int res2 =0 ;
        while (!queue.isEmpty()) {
            int curx = queue.peek().x;
            int cury= queue.peek().y;
            queue.poll();
            int cnt = 4;
            for (int i = 0; i < 4; i++) {
                int nx = curx+ dx[i];
                int ny = cury + dy[i];
                if(nx >=0 && ny >=0 && nx < n && ny < n && arr[ny][nx] == '#')
                    cnt--;
                if (nx >=0 && ny >=0 && nx < n && ny < n && !visit[ny][nx] && arr[ny][nx] =='#') {
                    queue.add(new Pair(nx, ny));
                    visit[ny][nx] = true;
                    res++;
                }
            }
            res2 += cnt;
        }
        if (result < res)
        {
            result = res;
            result2 = res2;
        }
        else if (result == res)
            result2 = Math.min(res2,result2);
    }

}