[백준]14502 - 연구소 문제 풀이(자바,Java)

문제

https://www.acmicpc.net/problem/14502

 

들어가며

오랜만에 푸는 문제라 숨 막혔다.

그리고 배열 복제하는 등의 테크닉도 배운 문제라 좋았다.

풀이 코드

package solved.ac.maraton;

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

public class 백준14502 {
    static int[][] arr;
    static int[][] map;
    static int n, m;
    static boolean[][] visited = new boolean[n][m];
    static int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    static int result = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt)
                .toArray();
        n = s[0]; m = s[1];
        arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        visited = new boolean[n][m];
        map = Arrays.stream(arr).map(int[]::clone)
                .toArray(int[][]::new);
        makeWall(0);
        System.out.println(result);
    }

    private static void makeWall(int count){
        if (count == 3){
            // 바이러스 처리
            int[][] tempMap = Arrays.stream(map).map(int[]::clone)
                    .toArray(int[][]::new);
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (!visited[i][j] && tempMap[i][j] == 2){
                        bfs(tempMap,i,j);
                    }
                }
            }
            int temp =0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (tempMap[i][j] == 0){
                        temp++;
                    }
                }
            }
            result = Math.max(result, temp);
            visited = new boolean[n][m];
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0){
                    map[i][j] = 1;
                    makeWall(count+1);
                    map[i][j] = 0;
                }
            }
        }
    }

    private static void bfs(int[][] tempMap, int startX, int startY){
        Queue<Position> queue = new ArrayDeque<>();
        queue.add(new Position(startX,startY));
        visited[startX][startY]= true;
        while (!queue.isEmpty()){
            Position poll = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nextX = poll.x + dirs[i][0];
                int nextY = poll.y + dirs[i][1];
                if (!isPass(tempMap,nextX,nextY)){
                    continue;
                }
                queue.add(new Position(nextX,nextY));
                visited[nextX][nextY] = true;
                tempMap[nextX][nextY] = 2;
            }
        }
    }
    private static boolean isPass(int[][] tempMap,int x, int y){
        if (x <0 || y < 0|| x >=n || y >=m
            || visited[x][y] || tempMap[x][y] != 0){
            return false;
        }
        return true;
    }
    private static class Position{
        int x;
        int y;

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

풀이

이 문제는 오히려 엄청 무식하게 접근하면 풀 수 있다.

그러면 무식한 방법이 뭘까?

바로 모든 경우의 수를 탐사하는 브루트 포스이다.

다음과 같은 흐름으로 진행한다.

 

1. 벽 3개를 설치하는 모든 경우를 탐사하고

2. 그 경우마다 바이러스를 BFS 돌려 안전 영역의 값을 구하고

3. 최대값인지 비교하고 저장한다.

 

2번과 3번은 비교적 익숙한 맛이라 쉬울 수 있다.

하지만 1번에서 처음 접근 시에 좀 문제가 생긴다.

이 수 많은 0 가운데 3개를 선택하는 걸 어떻게 구현할 수 있을까??

자바는 늘 이 조합 기법에서 문제가 생긴다. 귀찮고 그렇다.

조합 기법? 그러면 바로 백트래킹이 나와야 한다.

private static void makeWall(int count){
    if (count == 3){
        // 바이러스 처리
        int[][] tempMap = Arrays.stream(map).map(int[]::clone)
                .toArray(int[][]::new);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && tempMap[i][j] == 2){
                    bfs(tempMap,i,j);
                }
            }
        }
        int temp =0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tempMap[i][j] == 0){
                    temp++;
                }
            }
        }
        result = Math.max(result, temp);
        visited = new boolean[n][m];
        return;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 0){
                map[i][j] = 1;
                makeWall(count+1);
                map[i][j] = 0;
            }
        }
    }
}

그 중심이 바로 makeWall이라는 함수이다.

 

결국 2중 반복문으로 모든 빈 곳에 1을 넣는 것을 구현하고

만약 벽 3개를 다 놓았다면, bfs를 돌리면 된다.

이때, 기존 맵의 복사본을 bfs로 넘겨야 한다.

왜냐하면 기존 맵은 백트래킹으로 계속해서 변경되기 때문에 저장할 필요가 있기 때문이다.

그러면 2차원 배열을 어떻게 복사할까??

int[][] tempMap = Arrays.stream(map).map(int[]::clone)
        .toArray(int[][]::new);

stream 메소드를 사용하면 비교적 쉽게 할 수 있다.

 

모든 재귀가 끝나면 자연스럽게 답이 나오게 된다.