[랜덤 마라톤] Bacteria (Small)(12567)

1. 문제 풀이 아이디어

• 박테리아가 번식할 수 있는 가장 큰 테두리를 구한 뒤, 테두리의 최대 x좌표와 최대 y좌표를 더한 값에서 최소 x+y 좌표의 합을 뺀 뒤 1을 더하면 문제를 해결할 수 있다.

• 가장 큰 테두리는 BFS를 활용해 동, 서, 남, 북, 남서, 북동 방향으로 탐색하여 구한다.

2. 나의 정답 코드

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder stringBuilder = new StringBuilder();
        int t = Integer.parseInt(bufferedReader.readLine());
        int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {-1, 1}, {1, -1}};

        for (int i = 0; i < t; i++) {
            int n = Integer.parseInt(bufferedReader.readLine());
            boolean[][] v = new boolean[102][102];
            boolean[][] map = new boolean[102][102];
            List<int[]> list = new ArrayList<>();
            Queue<int[]> queue = new ArrayDeque<>();
            for (int j = 0; j < n; j++) {
                StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                int x1 = Integer.parseInt(stringTokenizer.nextToken());
                int y1 = Integer.parseInt(stringTokenizer.nextToken());
                int x2 = Integer.parseInt(stringTokenizer.nextToken());
                int y2 = Integer.parseInt(stringTokenizer.nextToken());
                for (int x = x1; x <= x2; x++) {
                    for (int y = y1; y <= y2; y++) {
                        map[x][y] = true;
                        list.add(new int[]{x, y});
                    }
                }
            }
            int result = 0;
            for (int[] cur : list) {
                if (v[cur[0]][cur[1]]) continue;
                v[cur[0]][cur[1]] = true;
                int maxX = 0;
                int maxY = 0;
                int minXY = Integer.MAX_VALUE;
                queue.add(cur);
                while (!queue.isEmpty()) {
                    cur = queue.poll();
                    maxX = Math.max(maxX, cur[0]);
                    maxY = Math.max(maxY, cur[1]);
                    minXY = Math.min(minXY, cur[0] + cur[1]);
                    for (int[] d : dir) {
                        int[] next = {cur[0] + d[0], cur[1] + d[1]};
                        if (v[next[0]][next[1]]) continue;
                        v[next[0]][next[1]] = true;
                        if (!map[next[0]][next[1]]) continue;
                        queue.add(next);
                    }
                }
                result = Math.max(result, maxX + maxY - minXY + 1);
            }
            stringBuilder.append("Case #").append(i + 1).append(": ").append(result).append('\n');
        }
        System.out.print(stringBuilder);
        bufferedReader.close();
    }
}

3. 정리

• 박테리아 좌표는 두 가지 자료구조에 저장한다.
• 리스트는 BFS 탐색 시 빠르게 박테리아를 찾아내기 위해 사용하며, 배열은 탐색 방향에 따라 효율적으로 접근하기 위해 활용한다.

• 리스트에서 박테리아의 좌표를 순회하며 BFS 탐색을 진행한다.

• BFS 탐색은 동, 서, 남, 북, 남서, 북동 방향으로 이루어지며, v와 map 2차원 배열을 사용해 다음 탐색할 박테리아를 찾는다.

• 탐색 중 최대 x좌표, 최대 y좌표, 최소 x+y 좌표를 계산한다.

• 탐색이 끝난 뒤, 현재 탐색된 테두리의 결과값이 더 크면 결과값을 갱신한다.

• 리스트는 박테리아를 빠르게 찾아 bfs로 탐색하기 위해, 배열의 경우 탐색 방향으로 접근을 위해 박테리아의 좌표를 두 가지 자료구조로 저장한다.

4. 시행착오

• 첫 번째 시도에서 단순 while문 구현으로 해결하려 했으나 시간 초과로 실패했다.
• 단순 구현으로도 해결된다고 했으나 Java에서는 시간이 부족했거나 잘못된 정보였다.

• 두 번째 시도에서는 누적 계산으로 해결하려 했으나 실패했다.
• 박테리아가 사라지는 경우를 고려하지 않아 단순 누적 계산으로는 해결이 불가능했다.

• 세 번째 시도에서는 BFS 탐색을 시도했지만, 북서쪽도 탐색 방향에 포함시켜 실패했다.
• 서쪽에 박테리아가 없고 북서쪽에만 박테리아가 있을 경우, 연결된 테두리가 아니다.
• 예시

0101 0000 0000
1010 0101 0000

0101 0000 0000 0000 0000
1110 0111 0011 0001 0000

• map[x][y]로 2차원 배열을 순회하며 박테리아 좌표를 찾는 것보다 리스트로 좌표를 저장해 사용하는 방식이 훨씬 효율적이었다.

5. 테스트 케이스