[알고리즘] 백준 14502 연구소 -dfs, bfs- 자바 코틀린

www.acmicpc.net/problem/14502

14502번: 연구소

 

 

백준 14502 연구소를 풀었습니다.

 

벽을 3개 세우고 바이러스를 퍼트리고 안전지역을 구하는 문제입니다.

 

다음과 같이 로직으로 풀었습니다.

 

1. 안전지역(0)에 모든 경우의 수로 벽을 3개 세운다  -백트랙킹-

 

2. 벽 3개를 세운 후 바이러스를 퍼트립니다. -bfs-

 

3. 안전구역의 최댓값을 구합니다.

 

문제를풀며 삽질했던 부분은 copy()가 깊은 복사가 안된다는 점입니다. 평소 1차원 배열은 깊은 복사가 되었던것같은데 2차원 배열에서는 안먹혀서 2중 반복문으로 새로 배열을 만들어주었습니다.

 

 

풀이는 다음과 같습니다.

 

[Java]

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static int[][] map;
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};
    private static int N;
    private static int M;
    private static ArrayList<Virus> virusList = new ArrayList<>();
    private static int answer = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        map = new int[N + 2][M + 2];
        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][M + 1] = 1;
        }
        for (int j = 0; j < map[0].length; j++) {
            map[0][j] = 1;
            map[N + 1][j] = 1;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 2) {
                    virusList.add(new Virus(i, j));
                }
            }
        }
        dfs(0);
        System.out.println(answer);
    }

    private static void dfs(int count) {
        if (count == 3) {
            //  int[][] tmpMap = map.clone();  deep copy 안됨
            int[][] tmpMap = new int[N + 2][M + 2];
            for (int i = 0; i <= N + 1; i++) {
                for (int j = 0; j <= M + 1; j++) {
                    tmpMap[i][j] = map[i][j];
                }
            }
            for (Virus virus : virusList) {
                spreadVirus(virus, tmpMap);
            }
            countSafeArea(tmpMap);
            return;
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(count + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

    private static void spreadVirus(Virus virus, int[][] map) {
        Queue<Virus> queue = new LinkedList<>();
        queue.offer(virus);
        while (!queue.isEmpty()) {
            Virus virus2 = queue.poll();
            for (int i = 0; i < 4; i++) {
                int x2 = virus2.x + dx[i];
                int y2 = virus2.y + dy[i];
                if (map[x2][y2] == 0) {
                    map[x2][y2] = 2;
                    queue.offer(new Virus(x2, y2));
                }
            }
        }
    }

    private static void countSafeArea(int[][] map) {
        int count = 0;
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (map[i][j] == 0) {
                    count++;
                }
            }
        }
        answer = Math.max(answer, count);
    }

    private static class Virus {
        int x;
        int y;

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

 

[Kotlin]

import java.util.*

private lateinit var map: Array<IntArray>
private val dx = intArrayOf(-1, 0, 1, 0)
private val dy = intArrayOf(0, -1, 0, 1)
private var N = 0
private var M = 0
private val virusList = ArrayList<Virus>()
private var answer = 0


fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    N = sc.nextInt()
    M = sc.nextInt()
    map = Array(N + 2) { IntArray(M + 2) }
    for (i in map.indices) {
        map[i][0] = 1
        map[i][M + 1] = 1
    }
    for (j in map[0].indices) {
        map[0][j] = 1
        map[N + 1][j] = 1
    }
    for (i in 1..N) {
        for (j in 1..M) {
            map[i][j] = sc.nextInt()
            if (map[i][j] == 2) {
                virusList.add(Virus(i, j))
            }
        }
    }
    dfs(0)
    println(answer)
}

private fun dfs(count: Int) {
    if (count == 3) { //  int[][] tmpMap = map.clone();  deep copy 안됨
        val tmpMap = Array(N + 2) { IntArray(M + 2) }
        for (i in 0..N + 1) {
            for (j in 0..M + 1) {
                tmpMap[i][j] = map[i][j]
            }
        }
        for (virus in virusList) {
            spreadVirus(virus, tmpMap)
        }
        countSafeArea(tmpMap)
        return
    }
    for (i in 1..N) {
        for (j in 1..M) {
            if (map[i][j] == 0) {
                map[i][j] = 1
                dfs(count + 1)
                map[i][j] = 0
            }
        }
    }
}

private fun spreadVirus(virus: Virus, map: Array<IntArray>) {
    val queue: Queue<Virus> = LinkedList()
    queue.offer(virus)
    while (!queue.isEmpty()) {
        queue.poll().run {
            for (i in 0..3) {
                val x2 = x + dx[i]
                val y2 = y + dy[i]
                if (map[x2][y2] == 0) {
                    map[x2][y2] = 2
                    queue.offer(Virus(x2, y2))
                }
            }
        }
    }
}

private fun countSafeArea(map: Array<IntArray>) {
    var count = 0
    for (i in 1..N) {
        for (j in 1..M) {
            if (map[i][j] == 0) {
                count++
            }
        }
    }
    answer = answer.coerceAtLeast(count)
}

data class Virus(var x: Int, var y: Int)