백준 14502번. 연구소 (Java, Python)

Problem

• 문제 링크 : https://www.acmicpc.net/problem/14502

벽 3개를 세운 뒤 바이러스를 퍼트렸을 때 가장 큰 안전 영역의 범위를 구하는 문제입니다.

Solution

문제를 보자마자 완전 탐색이라는 사실을 알 수 있습니다.

1. 벽을 3개 세운다
2. 바이러스를 퍼트린다.
3. 안전 구역의 갯수를 센다.
4. 제일 큰 값을 구한다.

이렇게 크게 4개의 순서로 이루어집니다.

백트래킹 을 통해서 벽 3개를 세울 수 있습니다.

n*m 개 중에서 3 개를 뽑는 Combination (조합) 을 구한다고 생각하면 됩니다.

기존에는 1차원 배열에서 구했던 조합을 2차원에서 구하는 것이 조금 어색할 수 있습니다.

숫자를 0 ~ n*m 까지 증가시킬때 (i/m, i%m) 을 좌표로 하면 2차원 배열의 모든 인덱스를 탐색할 수 있습니다.

예를 들어 n = 3, m = 2 인 3*2 배열을 탐색한다고 할 때

i	(i/, i%m)	좌표
0	(0/2, 0%2)	(0, 0)
1	(1/2, 1%2)	(0, 1)
2	(2/2, 2%2)	(1, 0)
3	(3/2, 3%2)	(1, 1)
4	(4/2, 4%2)	(2, 0)
5	(5/2, 5%2)	(2, 1)

이렇게 모든 좌표를 방문합니다.

파이썬은 i/m 을 구할 때 자동으로 실수형으로 바꿔주기 때문에 (int) i/m 으로 구하는 과정이 필요합니다.

추가) 파이썬은 // 연산자를 사용하면 정수형으로 리턴해준다고 합니다 (제보 감사합니다)

위의 규칙을 바탕으로 1차원 배열에서 조합을 구하듯이 해주시면 됩니다.

벽이 3개 세워진 후에는 맵을 복사합니다.

그리고 복사한 맵에 대해서 DFS를 통하여 바이러스를 퍼트립니다.

미리 값이 2인 좌표들을 따로 List에 저장하여 맵 전체를 스캔할 필요 없이 List만 순회하도록 합니다.

마지막으로 안전 구역을 구해서 MAX 값과 비교해서 갱신해주시면 됩니다.

Java Code

import java.util.*;
import java.io.*;

class Main {
    static class Dot {
        int x, y;

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

    static int n;
    static int m;
    static int[][] map;
    static int[][] copyed;
    static List<Dot> virusList = new ArrayList<Dot>();
    static int[] dx = {1, -1, 0, 0};
    static int[] dy = {0, 0, 1, -1};
    static int max = 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());
        map = new int[n][m];
        copyed = new int[n][m];

        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)
                    virusList.add(new Dot(i, j));
            }
        }

        setWall(0, 0);
        System.out.println(max);
    }

    // 백트래킹을 이용하여 3개의 벽 세우기
    static void setWall(int start, int depth) {
        if (depth == 3) {
            // 맵 복사
            copyMap();

            // 바이러스 퍼트리기
            for (Dot dot : virusList) {
                spreadVirus(dot.x, dot.y);
            }

            // 안전영역 크기 구하기
            max = Math.max(max, getSafeArea());
            return;
        }

        for (int i = start; i < n * m; i++) {
            int x = i / m;
            int y = i % m;

            if (map[x][y] == 0) {
                map[x][y] = 1;
                setWall(i + 1, depth + 1);
                map[x][y] = 0;
            }
        }
    }

    // 기존 맵을 유지하기 위해 바이러스 퍼트릴 맵 복사하기
    static void copyMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                copyed[i][j] = map[i][j];
            }
        }
    }

    // DFS 로 바이러스 퍼트리기
    static void spreadVirus(int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (copyed[nx][ny] == 0) {
                    copyed[nx][ny] = 2;
                    spreadVirus(nx, ny);
                }
            }
        }
    }

    static int getSafeArea() {
        int safe = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (copyed[i][j] == 0)
                    safe++;
            }
        }
        return safe;
    }
}

Python Code

# -*- coding: utf-8 -*-

import copy
import sys

n = m = 0
arr = []
virusList = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
maxVal = 0

## 안전구역 넓이 구하기
def getSafeArea(copyed):
    safe = 0
    for i in range(n):
        for j in range(m):
            if copyed[i][j] == 0:
                safe += 1
    return safe

## DFS로 바이러스 퍼트리기
def spraedVirus(x, y, copyed):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx and nx < n and 0 <= ny and ny < m:
            if copyed[nx][ny] == 0:
                copyed[nx][ny] = 2
                spraedVirus(nx, ny, copyed)

## 조합으로 벽 3개 놓는 모든 경우 구하기
def setWall(start, depth):
    global maxVal

    if depth == 3:
        # 복사
        copyed = copy.deepcopy(arr) 

        length = len(virusList)
        for i in range(length):
            [virusX, virusY] = virusList[i]
            spraedVirus(virusX, virusY, copyed)

        maxVal = max(maxVal, getSafeArea(copyed))
        return
    
    for i in range(start, n*m):
        x = i // m
        y = i % m

        if arr[x][y] == 0:
            arr[x][y] = 1
            setWall(i + 1, depth + 1)
            arr[x][y] = 0

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().split())
    for i in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))
    
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 2:
                virusList.append([i, j])

    ## 벽세우기
    setWall(0, 0)
    print(maxVal)