15. Baekjoon Gold4. '14502 - 연구소'

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

14502번: 연구소

 

BFS & 브루트포스를 활용한 문제이다.

한떄 BFS에 꽂혀서 BFS 문제만 풀었던 적이 있었는데,

오랜만에 이 유형을 다시 풀려니까 감을 잡는데 시간이 조금 걸렸다.

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

public class Q14502_연구소_gold4 {
    static int[][] map;
    static int safeZone, N, M;
    static List<int[]> virus;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        map = new int[N][M];
        virus = new ArrayList<>();
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                map[r][c] = in.nextInt();
                if (map[r][c] == 2) {
                    virus.add(new int[] { r, c });
                }
            }
        }

        int[][] mapCopy = new int[N][M];
        for (int r = 0; r < N; r++) {
            mapCopy[r] = map[r].clone();
        }

        int maxSafeZone = 0;

        // 0-N*M중 세개를 고르기
        for (int i = 0; i < N * M - 2; i++) {
            if (isWallOrVirus(i))
                continue; // 이미 벽이면 다음 포문으로

            for (int j = i + 1; j < N * M - 1; j++) {
                if (isWallOrVirus(j))
                    continue;

                for (int k = j + 1; k < N * M; k++) {
                    if (isWallOrVirus(k))
                        continue;
                    int[] list = new int[] { i, j, k };
                    // 벽 세우기
                    setWall(list);
                    spreadVirus();
                    // 세이프존 최댓값 갱신
                    maxSafeZone = Math.max(maxSafeZone, cntSafeZone());
                    // map 원상복구
                    for (int r = 0; r < N; r++) {
                        map[r] = mapCopy[r].clone();
                    }
                }
            }
        }
        System.out.println(maxSafeZone);
    }

    public static int cntSafeZone() {
        int cnt = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (map[r][c] == 0)
                    cnt++;
            }
        }
        return cnt;
    }

    public static boolean isWallOrVirus(int num) {
        int r = num / M;
        int c = num - r * M;

        if (map[r][c] == 1 || map[r][c] == 2) {
            return true;
        }
        return false;
    }

    public static void setWall(int[] list) {
        for (int i = 0; i < list.length; i++) {
            int num = list[i];
            int r = num / M;
            int c = num - r * M;

            map[r][c] = 1;
        }
    }

    public static void spreadVirus() {

        Queue<int[]> queue = new LinkedList<>();
        for (int[] node : virus) {
            queue.offer(node);
        }
        int[] dr = { -1, 0, 1, 0 };
        int[] dc = { 0, 1, 0, -1 };
        while (!queue.isEmpty()) {
            int[] par = queue.poll();
            for (int d = 0; d < 4; d++) {
                int nr = par[0] + dr[d];
                int nc = par[1] + dc[d];
                // 범위를 벗어나면 스킵
                if (outsideBorder(nr, nc))
                    continue;
                // 벽이면 스킵
                if (map[nr][nc] != 0)
                    continue;

                queue.offer(new int[] { nr, nc });
                map[nr][nc] = 2;
            }
        }
    }

    public static boolean outsideBorder(int r, int c) {
        return (r < 0 || c < 0 || r >= N || c >= M);
    }

}

 

정말 정직하게 문제에 주어진 조건을 하나하나 구현하듯이 코드를 짰다. 

3개의 벽을 세우는 부분에서 칸 3개를 고르는 과정을 for문으로 만들었는데, 벽의 개수가 더 많았더라면 재사용하기 힘든 코드이고

더 짧고 효율적인 코드가 있을것 같아 다른 풀이방법을 찾아보았다.

 

https://dingdingmin-back-end-developer.tistory.com/entry/%EB%B0%B1%EC%A4%80-14502%EC%9E%90%EB%B0%94-java-%EC%97%B0%EA%B5%AC%EC%86%8C

백준 14502[자바] java 연구소

 

위 블로그에서는 DFS를 활용하여 벽을 세우고 부수고를 반복했다. 

그리고 메서드안에 메서드를 중첩시키는 방식으로 구현했다.

 

public static void dfs(int depth) {
        if (depth == 3) {
            bfs();
            return;
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;
                    dfs(depth + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

이 부분!

활용법을 잘 익혀놔야겠다:)