[알고리즘 / 백준] 14502 - 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

 

문제는 위와 같으며, 새로운 3개의 벽을 세울 수 있는 모든 경우의 수를 확인하면서, 새로운 벽을 세웠을 때 바이러스가 퍼지는 것을 BFS 로 구한 뒤 전체 연구소 구역을 모두 확인하여 바이러스가 퍼지지 않은 구역의 수를 구해 기존 최대 안전 지역 수와 비교하여 더 큰수를 저장하였다가 최종적으로 출력하는 방식으로 문제를 해결하였습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
from itertools import combinations
import heapq

# 바이러스가 상하좌우로 이동할 수 있는 위치 저장
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# 바이러스가 퍼지는 것을 구현
def bfs():
    queue = []
    # 처음부터 바이러스가 있던 위치를 우선순위 큐에 저장하고 해당 위치를 방문한 것으로 처리
    for v in virus:
        heapq.heappush(queue, [0, v[0], v[1]])
        visited[v[0]][v[1]] = True

    while queue:
        cnt, cx, cy = heapq.heappop(queue)  # 현재 위치 정보를 가져와서

		# 상하좌우 방향으로 이동하면서
        for r in range(4):
            nx = cx + dx[r]
            ny = cy + dy[r]

            if 0 <= nx < n and 0 <= ny < m:  # 연구소 범위 내에 있고
                if labs[nx][ny] == 0 and not visited[nx][ny]:  # 바이러스가 퍼질 수 있는 공간이지만 아직 퍼지지 않은 경우
                    heapq.heappush(queue, [cnt + 1, nx, ny])  # 다음 위치를 우선 순위 큐에 넣고
                    visited[nx][ny] = True  # 다음 위치를 방문한 것으로(바이러스가 퍼진 것으로) 처리


n, m = map(int, stdin.readline().split())
labs = []
virus = []  # 초기 바이러스 위치 저장
combi = []  # 빈 공간 위치 저장

for i in range(n):
    tmp = list(map(int, stdin.readline().split()))
    for j in range(m):
        if tmp[j] == 2:
            virus.append([i, j])  # 처음부터 바이러스가 있는 위치 저장
        if tmp[j] == 0:
            combi.append([i, j])  # 빈 공간 위치 저장
    labs.append(tmp)  # 전체 정보 저장

max_safe_area = 0

# 3개의 벽을 세울 위치를 조합으로 구하기
for cb in combinations(combi, 3):
    # 새로운 벽 3개 세우기
    for c in cb:
        labs[c[0]][c[1]] = 1

    # 바이러스 퍼트리기
    visited = [[False] * m for _ in range(n)]
    bfs()

    # 감염되지 않은 칸 수 세기
    count = 0
    for i in range(n):
        for j in range(m):
            if not visited[i][j] and labs[i][j] == 0:  # 바이러스가 퍼지지 않은 빈 공간인 경우
                count += 1

    if count > max_safe_area:  # 현재 확인한 빈 공간의 수가 최대 안전 지역 수보다 큰 경우
        max_safe_area = count

    # 새로운 벽 3개 제거하기 (새로운 벽을 세우기 전 상태로 돌리기)
    for c in cb:
        labs[c[0]][c[1]] = 0

print(max_safe_area)

 

자바 코드는 다음과 같습니다. 파이썬과 같은 로직으로 풀려고 하였는데 26% 성공 후 틀렸다고 나오네요... 추후 다른 방식으로 풀이 후 수정된 코드를 올릴 수 있도록 하겠습니다! ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int[] dx = {-1, 1, 0, 0};
    private static int[] dy = {0, 0, -1, 1};

    private static int n;
    private static int m;

    private static int[][] labs;
    private static boolean[][] visited;

    private static ArrayList<int[]> virus = new ArrayList<>();
    private static ArrayList<int[]> combi = new ArrayList<>();

    private static int maxSafeArea = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        labs = new int[n][m];
        for (int i = 0; i < n; i++) {
            int[] tmp = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            for (int j = 0; j < m; j++) {
                if (tmp[j] == 0) {  // 초기 바이러스가 없고 벽을 세울 수 있는 빈 공간 위치 저장하기
                    combi.add(new int[]{i, j});
                } else if (tmp[j] == 2) {  // 초기 바이러스의 위치 저장하기
                    virus.add(new int[]{i, j});
                }

                labs[i] = tmp;
            }
        }

        for (int i = 0; i < combi.size() - 3; i++) {
            for (int j = i + 1; j < combi.size() - 2; j++) {
                for (int k = j + 1; k < combi.size() - 1; k++) {
                    // 새로운 벽 3개 세우기
                    int[] newWall = new int[]{i, j, k};
                    makeWall(newWall, true);

                    // 바이러스 퍼트리기
                    visited = new boolean[n][m];
                    bfs();

                    // 안전 지역 파악하기
                    int cnt = 0;
                    for (int a = 0; a < n; a++) {
                        for (int b = 0; b < m; b++) {
                            if (!visited[a][b] && labs[a][b] == 0) {
                                cnt += 1;
                            }
                        }
                    }

                    if (cnt > maxSafeArea) {
                        maxSafeArea = cnt;
                    }

                    // 새로 세운 벽 없애기
                    makeWall(newWall, false);
                }
            }
        }

        System.out.println(maxSafeArea);
    }

    private static void makeWall(int[] wall, boolean isBuilt) {
        if (isBuilt) {
            for (int w : wall) {
                labs[combi.get(w)[0]][combi.get(w)[1]] = 1;
            }
        } else {
            for (int w : wall) {
                labs[combi.get(w)[0]][combi.get(w)[1]] = 0;
            }
        }
    }

    private static void bfs() {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] t1, int[] t2) {
                return t1[0] - t2[0];
            }
        });

        for (int[] v : virus) {
            queue.offer(new int[]{0, v[0], v[1]});
            visited[v[0]][v[1]] = true;
        }

        while (!queue.isEmpty()) {
            int[] current = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nx = current[1] + dx[i];
                int ny = current[2] + dy[i];

                if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                    if (labs[nx][ny] == 0 && !visited[nx][ny]) {
                        queue.offer(new int[]{current[0] + 1, nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }
}