BOJ_14502 : 연구소

👉 문제링크

14502번: 연구소

---

---

🔸 문제 분석 🔸

• N x M 연구소 격자 맵에 빈 칸은 0, 벽은 1, 바이러스는 2로 입력된다.
  • 바이러스는 상하좌우 인접한 빈 칸으로 퍼져나간다.
  • 벽을 3개 세워서 바이러스가 다 퍼진 후 나올 수 있는 빈 칸의 수 최대값을 출력한다.
• 3개의 벽을 설치할 위치를 조합으로 구한다.
  • BFS로 바이러스가 퍼진 상태로 만든다.
  • 0의 수를 세서 최대값을 출력한다.

🔸 코드 🔸

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    private static int N, M, ans, cnt = -3;
    private static int[][] map, copy;
    private static Queue<Point> temp;
    private static ArrayList<Point> virus;
    private static int[] dr = {-1, 0, 1, 0};
    private static int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        // Input
        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];
        copy = new int[N][M];
        virus = new ArrayList<>();

        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] == 2)
                    virus.add(new Point(i, j));
                else if (map[i][j] == 0)
                    cnt++;
            }
        }

        // Combination
        comb(0, 0);

        // Output
        System.out.println(ans);
    }

    private static void comb(int cnt, int now) {
        if (cnt == 3) {
            ans = Math.max(ans, bfs());
            return;
        }

        for (int i = now; i < N * M; i++) {
            int r = i / M;
            int c = i % M;
            if (map[r][c] == 0) {
                map[r][c] = 1;
                comb(cnt + 1, i + 1);
                map[r][c] = 0;
            }
        }
    }

    private static int bfs() {
        deepCopy();

        temp = new ArrayDeque<>();
        for (Point p : virus) {
            temp.offer(p);
        }

        int add_virus = 0;
        while (!temp.isEmpty()) {
            Point point = temp.poll();

            for (int i = 0; i < dr.length; i++) {
                int r = point.r + dr[i];
                int c = point.c + dc[i];

                if (0<=r&&r<N&&0<=c&&c<M&&copy[r][c] == 0) {
                    copy[r][c] =2;
                    add_virus++;
                    temp.offer(new Point(r,c));
                }
            }
        }
        return cnt-add_virus;
    }

    private static void deepCopy() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy[i][j] = map[i][j];
            }
        }
    }
}

🔸 코드 해석 🔸

• 2차원 배열의 좌표를 기억히가 위해 Point 클래스를 만든다.
• N x M 연구실 입력값을 2차원 배열 map에 저장한다.
  • 바이러스의 초기 위치를 ArrayList형의 virus에 저장한다.
  • 빈 칸 0의 총 개수 cnt도 체크해둔다.
• comb() 메서드에서 세 벽의 위치를 조합으로 선택한다.
  • now 변수를 1씩 증가하며 몫과 나머지를 2차원 배열의 행과 열에 사용한다.
  • map의 벽을 세우는 좌표에 1을 넣고 comb를 재귀 호출한다.
  • 재귀 호출 후에는 다시 0을 넣어 원상복구한다.
  • 세운 벽의 개수 cnt가 3이 되면 bfs() 메서드를 호출하고, 0의 최대값 ans를 업데이트한다.
• bfs() 메서드에서 바이러스가 퍼지는걸 구현하고 0의 개수를 카운트해 반환한다.
  • deepCopy()메서드로 현재 map의 상태를 copy 배열에 복사한다.
  • 큐 temp에 바이러스 2의 위치들을 넣는다.
  • 큐 temp가 빌 때 까지 계산을 반복하고, 바이러스의 수(사라진 0의 수)를 체크한다.
    • 큐에 값을 꺼내 인접한 상하좌우를 확인하고 빈 칸이라면 0으로 값을 바꾼 뒤 해당 좌표를 큐에 넣는다.
  • cnt에서 add-virus를 뺀 값을 반환한다.

---

🔸 end 🔸

• 조합과 BFS를 함께 구현하는 문제였다.
• comb() 메서드에서 효율성을 높이고자 for문 조건을 잘못 지정해서 1회 틀렸다.
  • 조금 중복이 일어나더라도 반례가 없는 확실한 조건이 더 나은 것 같다.