[백준 14502] 연구소 - JAVA

과거에 풀었던 문제입니다. 노션에 기록된 내용을 바탕으로 정리했습니다.

문제 정의

• 목표: 연구소의 빈 칸 중 3곳에 벽을 세워, 바이러스가 퍼진 후 남게 되는 안전 영역(빈 칸)의 최대 크기를 구하기
• 입력 (Input):
  1. N, M: 지도의 세로와 가로 크기
  2. int[][] area: 연구소의 상태 (0: 빈 칸, 1: 벽, 2: 바이러스)
• 출력 (Output):
  • int: 얻을 수 있는 안전 영역의 최대 크기
• 핵심 조건:
  • 새로운 벽은 반드시 3개를 빈 칸에 세워야 한다.
  • 벽을 세운 뒤, 바이러스는 상하좌우의 인접한 빈 칸으로 모두 퍼져나간다.
  • 안전 영역은 바이러스가 퍼지지 않은 빈 칸(0)의 총 개수

접근 방법

• 벽 세우기 (백트래킹):
  • 백트래킹 재귀 함수를 이용해, 지도의 빈 칸(0) 중 3곳을 선택하는 모든 경우의 수를 탐색
  • 벽 3개가 모두 선택되면, 해당 지도 상태에서 바이러스 전파 시뮬레이션을 시작
• 바이러스 전파 (BFS):
  • 벽이 3개 세워진 각 지도 상태에 대해, 초기 바이러스 위치에서부터 너비 우선 탐색(BFS)을 실행
  • BFS를 통해 바이러스가 퍼져나가는 과정을 모의실험하고, 최종적으로 남은 안전 영역의 크기를 계산
• 상태 복구 및 정답 갱신:
  • 한 번의 BFS 시뮬레이션이 끝나면, 바이러스가 새로 퍼졌던 영역과 세웠던 벽을 다시 원래의 빈 칸 상태로 되돌리기
  • 매 시뮬레이션마다 계산된 안전 영역의 크기를 기존의 최대값과 비교하여 갱신

코드

python code

from sys import stdin
from collections import deque

N, M = map(int, stdin.readline().split())
A = [list(map(int, stdin.readline().split())) for _ in range(N)]
break_point = N * M
virus = deque([])
m = 0

for i in range(N):
    for j in range(M):
        if A[i][j] == 2:
            virus.append((i, j))

def bfs(li):
    global m
    area = [arr[:] for arr in A]
    start = virus.copy()

    while li:
        i, j = li.pop()
        area[i][j] = 1
    
    while start:
        i, j = start.popleft()

        for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            ni, nj = di+i, dj+j
            if 0 <= ni < N and 0 <= nj < M and not area[ni][nj]:
                area[ni][nj] = 2                
                start.append((ni, nj))

    cnt = 0 
    for i in range(N):
        for j in range(M):
            if not area[i][j]:
                cnt += 1

    m = max(m, cnt)

def broute_force(n, p, li):
    if n == 3:
        bfs(li)
        return
    
    if p == break_point:
        return
    
    i = p // M
    j = p % M

    if A[i][j] == 0:
        broute_force(n+1, p+1, li + [(i, j)])
    broute_force(n, p+1, li)

broute_force(0, 0, [])
print(m)

deepCopy 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

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

public class Main {
    static StringTokenizer st;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] area = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                area[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bt(0, 0, 0, N, M, area);
        System.out.println(answer);
    }

    static void bt(int wallCount, int y, int x, int N, int M, int[][] area) {
        if (wallCount == 3) {
            answer = Math.max(answer, spread(N, M, area));
            return;
        }

        for (int i = y; i < N; i++) {
            for (int j = (i == y) ? x : 0; j < M; j++) {
                if (area[i][j] == 0) {
                    area[i][j] = 1;
                    bt(wallCount + 1, i, j + 1, N, M, area);
                    area[i][j] = 0;
                }
            }
        }
    }

    static int spread (int N, int M, int[][] area) {

        int[][] areaCopy = new int[N][M];

        for (int i = 0; i < N; i++) {
            System.arraycopy(area[i], 0, areaCopy[i], 0, M);
        }

        int count = N * M;
        boolean[][] visited = new boolean[N][M];
        ArrayDeque<Node> q = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (area[i][j] != 0) {
                    count--;
                    if (area[i][j] == 2) {
                        q.offer(new Node(i, j));
                        visited[i][j] = true;
                    }
                }
            }
        }

        while (!q.isEmpty()) {
            Node node = q.poll();
            int y = node.y;
            int x = node.x;

            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx] && areaCopy[ny][nx] == 0) {
                    count--;
                    areaCopy[ny][nx] = 2;
                    visited[ny][nx] = true;
                    q.offer(new Node(ny, nx));
                }
            }
        }

        return count;
    }
}

spread 메서드 호출마다 원본 area 배열을 유지시키기 위해 areaCopy라는 area 배열의 deepcopy본을 활용해

감염되지 않은 영역을 구했습니다.

현재 area의 범위가 8로 매우 좁은 범위로 제한되어 있어서

spread 메서드 호출마다 deepcopy를 사용하는 방식으로 구현했습니다.

DeepCopy 방법 비교

방법	성능 (속도)	가독성 및 간결성	추천 상황
System.arraycopy()	최상	하	최고의 성능이 반드시 필요한 경우
Arrays.copyOf()	상	상	성능과 가독성의 균형이 필요할 때 (가장 무난한 선택)
반복문 (For Loop)	중	중	알고리즘을 공부하거나 동작을 명확히 이해하고 싶을 때
스트림 (Stream)	하	최상	코드의 간결함을 최우선으로 할 때 (성능이 중요하지 않은 경우)

deepCopy에는 여러가지 방법이 있는데 그 중 가장 성능(속도) 이 좋은 System.arraycopy를 사용했습니다.

그러나 재귀를 할 때마다 deepCopy를 하는 것은 비효율적이라고 생각해서

원본 area를 해치지 않으면서 감염되지 않은 구역을 계산하고 다시 복구하는 방법을 고민했습니다.

큐를 활용한 복원 방법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

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

public class Main {
    static StringTokenizer st;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static int answer = 0;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] area = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                area[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        bt(0, 0, 0, N, M, area);
        System.out.println(answer);
    }

    static void bt(int wallCount, int y, int x, int N, int M, int[][] area) {
        if (wallCount == 3) {
            answer = Math.max(answer, spread(N, M, area));
            return;
        }

        for (int i = y; i < N; i++) {
            for (int j = (i == y) ? x : 0; j < M; j++) {
                if (area[i][j] == 0) {
                    area[i][j] = 1;
                    bt(wallCount + 1, i, j + 1, N, M, area);
                    area[i][j] = 0;
                }
            }
        }
    }

    static int spread (int N, int M, int[][] area) {

        int count = N * M;
        boolean[][] visited = new boolean[N][M];
        ArrayDeque<Node> q = new ArrayDeque<>();
        ArrayDeque<Node> infestedArea = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (area[i][j] != 0) {
                    count--;
                    if (area[i][j] == 2) {
                        q.offer(new Node(i, j));
                        visited[i][j] = true;
                    }
                }
            }
        }

        while (!q.isEmpty()) {
            Node node = q.poll();
            int y = node.y;
            int x = node.x;

            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx] && area[ny][nx] == 0) {
                    count--;
                    area[ny][nx] = 2;
                    visited[ny][nx] = true;
                    q.offer(new Node(ny, nx));
                    infestedArea.offer(new Node(ny, nx));
                }
            }
        }

        while (!infestedArea.isEmpty()) {
            Node node = infestedArea.poll();
            area[node.y][node.x] = 0;
        }

        return count;
    }
}

생각보다 최적화 되지 않았습니다.

속도 면에서는 약 15% 가량의 성능 개선이 이루어졌지만

메모리 사용량이 약 1.5배가 되었습니다.

우선 첫 번째 문제점을 발견했습니다.

매 spread 메서드에서 이중 for문을 사용해 비효율이 발생했습니다.

이 부분을 메인 메서드에 이동하고 visited 또한 복원 방식으로 사용하는 것으로 코드를 작성했습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

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

public class Main {
    static StringTokenizer st;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    static boolean[][] visited;
    static ArrayDeque<Node> init;
    static int answer = 0;
    static int initCount;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] area = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                area[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        initCount = (N * M) - 3;
        visited = new boolean[N][M];
        init = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (area[i][j] != 0) {
                    initCount--;
                    if (area[i][j] == 2) {
                        init.offer(new Node(i, j));
                        visited[i][j] = true;
                    }
                }
            }
        }

        bt(0, 0, 0, N, M, area);
        System.out.println(answer);
    }

    static void bt(int wallCount, int y, int x, int N, int M, int[][] area) {
        if (wallCount == 3) {
            answer = Math.max(answer, spread(N, M, area));
            return;
        }

        for (int i = y; i < N; i++) {
            for (int j = (i == y) ? x : 0; j < M; j++) {
                if (area[i][j] == 0) {
                    area[i][j] = 1;
                    bt(wallCount + 1, i, j + 1, N, M, area);
                    area[i][j] = 0;
                }
            }
        }
    }

    static int spread (int N, int M, int[][] area) {
        ArrayDeque<Node> q = new ArrayDeque<>(init);
        ArrayDeque<Node> infestedArea = new ArrayDeque<>();
        int count = initCount;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int y = node.y;
            int x = node.x;

            for (int d = 0; d < 4; d++) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < N && 0 <= nx && nx < M && !visited[ny][nx] && area[ny][nx] == 0) {
                    count--;
                    area[ny][nx] = 2;
                    visited[ny][nx] = true;
                    q.offer(new Node(ny, nx));
                    infestedArea.offer(new Node(ny, nx));
                }
            }
        }

        while (!infestedArea.isEmpty()) {
            Node node = infestedArea.poll();
            area[node.y][node.x] = 0;
            visited[node.y][node.x] = false;
        }

        return count;
    }
}

조금 더 성능이 개선됐지만 제가 원하는 수준까지는 최적화 되지 않았습니다.
추후 시간이 날 때 조금 더 고민하고 최적화 해볼 예정입니다.