백준 14502 자바

<문제>

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

14502번: 연구소

 

<풀이>

위 문제 같은 경우 벽을 3개를 세울 수 있다. 또한 N,M의 범위가 매우 작다. 그래서 나는 dfs 와 bfs를 하나씩 이용해서 풀어야 된다는 생각을 했다.

맨처음에 map 을 입력받는다. 이 맵과 벽이 생길때마다 해당 맵을 clone()을 통해 복사해서 사용을 해야한다.먼저 벽을 세우는 곳을 dfs로 푼다. 그리고 벽이 3개가 됐을 경우에는 bfs로 넘어가서 바이러스가 갈 수 있는 모든 곳을 2로 변경한다. 이후 안전영역의 크기를 2차원 반복문을 이용해 가장 큰 안전영역을 구해서 출력하면 된다. 

해당 문제를 풀때 다른 bfs문제처럼 boolean 값을 가질 수 있는 이차원 배열 visited를 만들었지만, 바이러스가 퍼진 곳에 값을 2로 바꾸면 되기 때문에 visited 배열이 필요 없게 되었다.

 

난이도가 올라갈수록 하나의 문제에 하나의 알고리즘이 쓰이지 않는다는 것을 기억해야한다. 위 문제는 그래도 비슷한 그래프 탐색 알고리즘이 쓰였지만, 다른 알고리즘 2개가 사용될 수 있다는 것을 생각을 해야할거같다.

 

<코드>

import java.util.*;
import java.io.*;
public class Main {
    public static int n;
    public static int m;
    public static int[][] map;
    public static int[] dx = {-1,1,0,0};
    public static int[] dy = {0,0,-1,1};

    public static int safeZoneSize = 0;


    public static void main(String[] args)throws IOException {
        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];
        for(int i = 0; i < n; i++) { // 입력
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            for(int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st2.nextToken());
            }
        }
        dfs(0);
        System.out.println(safeZoneSize);
    }
    public static void dfs(int cnt) {
        if(cnt == 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(cnt + 1);
                    map[i][j] = 0;
                }
            }
        }
    }
    public static void bfs() {
        Queue<int[]> queue = new LinkedList<>();

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 2) {
                    queue.add(new int[] {i,j});
                }
            }
        }
        int[][] copyMap = new int[n][m];

        for(int i = 0; i < n; i++) {
            copyMap[i] = map[i].clone();
        }

        while(!queue.isEmpty()) {
            int now[] = queue.poll();
            int nowX = now[0];
            int nowY = now[1];
            for(int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if(nextX < 0 || nextY < 0 || nextX >=n || nextY >= m) continue;
                if(copyMap[nextX][nextY] == 0) {
                    queue.add(new int[] {nextX, nextY});
                    copyMap[nextX][nextY] = 2;
                }
            }
        }
        safeZone(copyMap);
    }

    public static void safeZone(int[][] copyMap) {
        int size = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(copyMap[i][j] == 0) size++;
            }
        }
        safeZoneSize = Math.max(safeZoneSize, size);
    }
}