[백준] 16932 모양 만들기 - Java

 

 

문제 출저

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

16932번: 모양 만들기

 

 

 

문제 풀이

0과 1이 주어진 숫자판에서 0을 1로 바꿨을 때 1이 이어진 가장 큰 넓이가 무엇인지 구하는게 이 문제의 요구사항이다.

 

숫자판을 입력 받을 때 0을 저장하는 zeroQue를 만든다.

또한 1이 이어진 영역의 넓이를 구하기 위해 BFS를 사용한다. 이 때 인덱스를 부여하여 탐사간 마친 1의 영역은 인덱스 번호로 바꾼다. Map<Integer, Integer> areaMap을 만들어 인덱스에 따른 넓이를 저장한다.

 

zeroQue에 저장된 0을 하나씩 꺼내어 4방향을 탐색한다. 

인덱스 번호가 있으면 Set<Integer> indexSet에 저장했다. Set을 사용한 이유는 중복을 방지하기 위해서 이다.

이러면 4방향을 탐색했을 때 영역의 인덱스가 indexSet에 담긴다.

indexSet에서 인덱스를 하나씩 꺼내 areaMap에서 인덱스에 해당하는 영역을 가져와 모두 더한다.

마지막으로 자기 자신을 0에서 1로 바꾸었으니 +1을 하여 그 부분을 0에서 1로 바꿨을 때 영역을 구하게 된다.

int answer 변수에 영역이 가장 큰 크기를 업데이트해서 최종 가장 큰 영역을 구합니다. 

 

 

 

소스 코드 

package baekjoon.backjoon9.day2;

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

/*
모양 만들기
https://www.acmicpc.net/problem/16932
 */


public class B16932 {

    static int n;
    static int m;
    static int[][] board;

    static Queue<dot> zeroQue;
    static Map<Integer, Integer> areaMap;
    static boolean[][] visited;

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

    static int answer;

    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());
        m = Integer.parseInt(st.nextToken());
        board = new int[n][m];
        zeroQue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
                if(board[i][j] == 0) {
                    zeroQue.add(new dot(i, j));
                }
            }
        }

        // 영역의 넓이를 구하고 인덱싱 하기
        areaMap = new HashMap<>();
        findArea();

        // zeroQue 에서 0인 것을 꺼내 4방향을 탐색에 연결했을 때 가장 큰 영역을 answer에 계속 업데이트 한다.
        findAnswer();

        // 정답 출력
        StringBuilder sb = new StringBuilder();
        sb.append(answer);
        System.out.println(sb);


    }


    public static void findAnswer() {

        while (!zeroQue.isEmpty()) {
            int result = 1;
            dot d = zeroQue.poll();
            Set<Integer> indexSet = new HashSet<>();
            for (int i = 0; i < 4; i++) {
                int ny = d.y + dy[i];
                int nx = d.x + dx[i];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m) {
                    if (board[ny][nx] != 0) {
                        indexSet.add(board[ny][nx]);
                    }
                }
            }

            for (int index : indexSet) {
                result += areaMap.get(index);
            }

            answer = Math.max(answer, result);

        }
    }


    public static void findArea() {
        visited = new boolean[n][m];
        int index = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(board[i][j] == 1 && visited[i][j] == false) {
                    index += 1;
                    int area = calculateArea(i, j, index);
                    areaMap.put(index, area);
                }
            }
        }
    }

    public static int calculateArea(int y, int x, int index) {
        visited[y][x] = true;
        Queue<dot> que = new LinkedList<>();
        que.add(new dot(y, x));
        int area = 1;
        board[y][x] = index;

        while (!que.isEmpty()) {
            dot d = que.poll();

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

                if(check(ny, nx)) {
                    visited[ny][nx] = true;
                    board[ny][nx] = index;
                    que.add(new dot(ny, nx));
                    area += 1;
                }
            }

        }

        return area;

    }

    // 범위 안에 있고 1인 경우
    // true : 탐색 가능, false : 탐색 불가능
    public static boolean check(int y, int x) {
        if (y >= 0 && y < n && x >= 0 && x < m && board[y][x] == 1) {
            return true;
        }
        return false;
    }



    public static class dot {
        int y;
        int x;

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




}