[백준] 16932번 : 모양 만들기

문제

www.acmicpc.net/problem/16932

16932번: 모양 만들기

문제해결방법

이 문제를 해결하기 위해, 0인 곳을 1로 만들어서 상, 하, 좌, 우에 있는 모양들이 연결되도록 하고, 그 결과로 만들어지는 가장 큰 모양을 찾아야 겠다고 생각했다.

1. 처음에 배열을 돌면서 BFS를 통해 연결 요소들을 찾아 각 연결 요소에 번호를 붙이고 Map에 그 번호를 Key로 사이즈를 Value로 해서 저장해줬다.

2. 다시 한 번 배열을 돌면서 0인 곳마다 상, 하, 좌, 우를 탐색하며 만약 인접한 곳이 0이 아닌 다른 값이라면 Map에서 해당 값을 Key로 하는 Value(연결 요소의 사이즈)를 가져와 더해줬다.
* 인접한 요소들이 중복이 될 수 있으므로 Set에 넣어서 중복을 제거해줬다.

3. 2번 과정을 진행하며 계산된 크기중에 가장 큰 사이즈가 가장 큰 모양의 사이즈이다.

코드

package baekjoon;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
 
public class Main16932_모양만들기 {
    public static int N, M, max = 0;
    public static int[][] map;
    public static int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    public static Map<Integer, Integer> land = new HashMap<Integer, Integer>();
    
    public static void bfs(int i, int j, int key) {
        int count = 1;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{i, j});
        map[i][j] = key;
        while(!q.isEmpty()) {
            int[] cur = q.poll();
            for(int d=0; d<dir.length; d++) {
                int x = cur[0] + dir[d][0];
                int y = cur[1] + dir[d][1];
                if(x>=0 && x<N && y>=0 && y<M && map[x][y]==1) {
                    map[x][y] = key;
                    count++;
                    q.add(new int[]{x, y});
                }
            }
        }
        land.put(key, count);
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        map = new int[N][M];
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) map[i][j] = s.charAt(j*2)-'0';
        }
        int key = 2;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j]==1) bfs(i, j, key++);
            }
        }
        Set<Integer> keySet = new HashSet<Integer>();
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(map[i][j]==0) {
                    keySet.clear();
                    int size = 1;
                    for(int d=0; d<dir.length; d++) {
                        int x = i + dir[d][0];
                        int y = j + dir[d][1];
                        if(x>=0 && x<N && y>=0 && y<M && map[x][y]!=0) {
                            keySet.add(map[x][y]);
                        }
                    }
                    for(int k : keySet) {
                        size += land.get(k);
                    }
                    if(max<size) max = size;
                }
            }
        }
        System.out.println(max);
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.