[BOJ] 16932: 모양 만들기 (JAVA)

문제

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

 

여담

시간 초과가 진짜 많이 발생했다. 오랜만에 골드 BFS 문제를 푸니까 좀 어지럽다. 계속 쉬운 문제만 푸려고 하는 습관을 버려야지 진짜..

 

암튼 처음에는 map[i][j] 값이 0일 때마다 BFS 탐색을 수행하면 되겠다고 생각했다. 그치만 위와 같이 시간 초과가 발생했다. 시간을 줄일 수 있는 방법으로 고쳐나갔는데도 계속 시간 초과가 발생해서 결국 다른 분의 아이디어를 참고했다. 

 

항상 문제를 풀 때 시간 초과를 고려해서 푸는 습관을 들이도록 노력해야지..!

 

풀이

위에서 언급했듯이, map[i][j]의 값이 0이면 BFS 탐색을 수행해서 모양의 최대 넓이를 구하는 방식을 사용하면 시간 초과가 발생한다. 따라서 다음과 같은 순서대로 문제를 풀면 된다.

1. 1으로만 구성되고 연결된 그룹 찾기
2. map[i][j]가 0인 곳에서 상하좌우에 그룹이 존재하는지 확인하기
3. 그룹이 존재한다면 해당 그룹의 넓이(= 연결된 칸의 수)를 더하기

 

이때, 각 그룹을 구별해야 해당 그룹에 포함된 수를 구할 수 있다. 따라서 다음과 같이 그룹에 수를 부여해서 구분할 수 있도록 해야 한다.

 

코드

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static ArrayList<Pos> zeroList = new ArrayList<>();
    static ArrayList<Pos> oneList = new ArrayList<>();
    static HashMap<Integer, Integer> group = new HashMap<>(); // 그룹 번호, 그룹의 크기
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};

    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());
        map = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if (map[i][j] == 0) zeroList.add(new Pos(i, j)); // 칸에 들어있는 수가 0이면 따로 저장하기
                else oneList.add(new Pos(i, j));
            }
        }

        // 그룹 찾기
        int groupNum = 1;
        for (Pos pos : oneList) {
            if (!visited[pos.x][pos.y]) { // map[i][j]가 1인 것들은 이미 방문 처리가 완료됨
                findGroup(pos.x, pos.y, groupNum++);
            }
        }

        // 그룹 연결하기
        int maxArea = 0;
        for (Pos pos : zeroList) {
            maxArea = Math.max(maxArea, linkedGroup(pos.x, pos.y));
        }
        System.out.println(maxArea);
    }

    static void findGroup(int x, int y, int groupNum) { // 그룹 찾기
        Queue<Pos> queue = new LinkedList<>();
        queue.offer(new Pos(x, y));
        visited[x][y] = true;

        int area = 0;
        while (!queue.isEmpty()) {
            Pos now = queue.poll();
            map[now.x][now.y] = groupNum;
            area++;

            for (int i = 0; i < 4; i++) {
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if (nx < 0 || ny < 0 || nx >= N || ny >= M || visited[nx][ny] || map[nx][ny] == 0) {
                    continue;
                }

                queue.offer(new Pos(nx, ny));
                visited[nx][ny] = true;
            }
        }
        group.put(groupNum, area);
    }

    static int linkedGroup(int x, int y) { // map[i][j]의 값을 0에서 1로 변경한 후, 그룹과 연결하기
        HashSet<Integer> checkGroup = new HashSet<>();
        int area = 1;
        for (int i = 0; i < 4; i++) { // 현재 위치를 기준으로 네 방향 중에 그룹이 있는지만 찾으면 됨!
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= M || map[nx][ny] == 0) {
                continue;
            }

            int groupNum = map[nx][ny];
            if (!checkGroup.contains(groupNum)) {
                area += group.get(groupNum);
                checkGroup.add(groupNum);
            }
        }
        return area;
    }

    static class Pos {
        int x;
        int y;

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

---

참고

https://suhyeokeee.tistory.com/75