Baekjoon 14502 연구소

문제 이해

Baekjoon 14502 연구소

2차원 평면에 빈 공간(0)과 벽(1)과 바이러스(2)가 있다.

바이러스는 빈 공간을 따라 상하좌우로 전파될 수 있고, 벽은 통과하지 못한다.

벽을 세 개 더 세울 때, 바이러스가 침투하지 못하는 가장 많은 안전구역을 얻을 수 있는 경우를 찾아서 안전구역의 갯수를 구하는 문제이다.

입출력 조건 확인

입력 조건(맵의 크기가 최대 8 × 8)이 매우 작고, 시간 제한(2초)과 메모리 제한(512MB)이 여유롭게 설정되어 있다.

문제 풀이 내용 정리

1. 맵 그리기
   입력 받은 대로 맵을 그린다.

2. 추가 벽 경우의 수
   벽을 세울 수 있는 위치를 가져와서 세울 수 있는 모든 경우의 수를 구한다.

3. 경우의 수 만큼 반복
   구한 경우의 수 만큼 반복하여 맵을 초기화하고, 벽을 세우고, 바이러스를 퍼뜨리고, 안전구역을 계산한다.

Java

Baekjoon Source

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.awt.Point;

public class Main {
    static byte[][] map;
    static byte[][] testMap;
    static ArrayList<Point[]> wallCase = new ArrayList<>();
    static ArrayList<Point> zeroPoint = new ArrayList<>();
    static Queue<int[]> queue = new LinkedList<>();
    static int[] dX = {1, -1, 0, 0};
    static int[] dY = {0, 0, 1, -1};
    static int count = 0;

    static void copyMap () {
        for (int i = 0; i < map.length; i++) {
            testMap[i] = map[i].clone();
        }
    }

    // 탐색
    static void simulation (int a, int b) {
        while (queue.size() > 0) {
            int[] tmp = queue.poll();
            for (int i = 0; i < 4; i++) {
                Point next = new Point(tmp[0] + dX[i], tmp[1] + dY[i]);
                if (next.x >= 0 & next.y >= 0 & next.x < testMap.length & next.y < testMap[0].length) {
                    if (testMap[next.x][next.y] == a) {
                        count++;
                        testMap[next.x][next.y] = (byte) b;
                        queue.offer(new int[] {next.x, next.y});
                    }
                }
            }
        }
    }

    // 벽을 세울 수 있는 경우의 수 작성
    static void buildWall () {
        Point[] wall = new Point[3];

        for (int i = 0; i < zeroPoint.size(); i++) {
            for (int j = 0; j < zeroPoint.size(); j++) {
                for (int k = 0; k < zeroPoint.size(); k++) {
                    wall = new Point[]{zeroPoint.get(i), zeroPoint.get(j), zeroPoint.get(k)};
                    if (wall[0].equals(wall[1]) | wall[0].equals(wall[2]) | wall[1].equals(wall[2]))
                        break;
                        wallCase.add(wall.clone());
                }
            }
        }            
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        String[] mapSize = sc.nextLine().split(" ");
        map = new byte[Integer.parseInt(mapSize[0])][Integer.parseInt(mapSize[1])];
        testMap = new byte[map.length][map[0].length];

        // 입력받은 내용으로 Map 생성
        for (int i = 0; i < map.length; i++) {
            String[] tmp = sc.nextLine().split(" ");
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = (byte) Integer.parseInt(tmp[j]);

                // 도는 김에 벽 세울 수 있는 위치도 같이 받자
                if (map[i][j] == 0) zeroPoint.add(new Point(i, j));
            }
        }
        
        buildWall();

        // 벽을 세울 수 있는 경우의 수 만큼 반복
        int result = 0;
        for (int i = 0; i < wallCase.size(); i++) {
            copyMap();

            // 추가할 벽을 맵에 작성
            for (int j = 0; j < wallCase.get(0).length; j++) {
                testMap[wallCase.get(i)[j].x][wallCase.get(i)[j].y] = 1;
            }

            // 바이러스 전파
            for (int j = 0; j < testMap.length; j++) {
                for (int k = 0; k < testMap[0].length; k++) {
                    if (testMap[j][k] == 2) {
                        testMap[j][k] = 3;
                        queue.offer(new int[] {j, k});
                        simulation(0, 3);
                    }
                }
            }

            // 안전구역 확인
            count = 0;
            for (int j = 0; j < testMap.length; j++) {
                for (int k = 0; k < testMap[0].length; k++) {
                    if (testMap[j][k] == 0) {
                        testMap[j][k] = 8;
                        count++;
                        queue.offer(new int[] {j, k});
                        simulation(0, 8);
                        if (result < count) {
                            result = count;
                        }
                    }
                }
            }
        }
        System.out.println(result);
    }
}

코드 문제점 및 해결 방법

1. 경우의 수 최적화
   처음에 입력 조건을 자세히 확인하지 않고 코드를 짜다 보니 경우의 수가 중복해서 너무 많아지는 것 같아서 중복을 제거하려고 엄청나게 고민했다.
   결과적으로 그 코드는 빼고 제출해도 맞기는 했는데, 이 방법에 대해서는 나중에라도 더 찾아보고 해결해야 할 것 같다.

2. 안전구역 확인 문제
   테스트 케이스 예제 1, 2가 각각 1씩 낮은 결과가 계속 나오는 문제가 발생했다.
   코드가 완벽히 만들어졌다고 생각했는데 1씩만 빠지니까 답을 전혀 찾지 못하고 있었다.
   알고보니 하나의 시작점에 대해서만 확인을 하게 코드가 짜져 있어서 수정하고 완성했다. ㅠㅠ