[백준 BOJ/Gold IV] 14502번 : 연구소

 

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

14502번: 연구소

 

정말 잔인한 문제였다 dfs와 bfs를 함께 써야 풀 수 있는 문제😨😨

세상엔 참 다양한 문제가 있음을 느꼈다

 

 

이 문제는 벽 3개를 다양하게 세워보면서 2가 가장 덜 퍼지는(=0이 가장 많이 남는) 경우를 구해야한다

 

1. 벽 3개를 다양하게 세우기

    static void dfs(int wall) { // 벽 세우는 경우의 수
        if (wall == 3) {
            bfs(); // 벽이 3개 세워지면 바이러스 퍼지는거 확인
            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(wall + 1);
                    map[i][j] = 0;
                }
            }
        }
    }

 

- 0이면 벽을 세울 수 있는 곳이므로 0을 만나면 1로 바꿔준다(=벽을 세운다)

- 3개가 채워지면 바이러스 퍼지는것을 확인해야하므로 bfs()로 이동한다

- 확인하고 돌아오면 1로 바꿨던 자리들을 다시 0으로 돌린다

 

 

2. 바이러스 퍼지는거 확인

static void bfs() { // 바이러스 퍼지는거 확인
        Deque<int[]> dq = new ArrayDeque<>();
        virus = new int[N][M]; // bfs 새로 들어올때마다 초기화됨

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                virus[i][j] = map[i][j];
                if(virus[i][j] == 2) {
                    dq.addLast(new int[] {i, j});
                }
            }
        }

        while (!dq.isEmpty()) {
            int[] xy = dq.pollFirst();
            int x = xy[0];
            int y = xy[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (virus[nx][ny] == 0) {
                        dq.addLast(new int[]{nx, ny});
                        virus[nx][ny] = 2;
                    }
                }
            }
        }

 

- 바이러스가 퍼지는것을 확인하는 배열을 새로 만들어줄건데 map값을 그대로 넣어주면서 바이러스가 있는 위치인 2를 만나면 큐에 담아준다

- 큐에 들어있는것을 하나씩 꺼내면서 꺼낸 위치의 상하좌우를 확인한다 전체 배열 크기를 벗어나지 않으면서 0인 위치가 잇다면 값을2로 바꿔준다

 

⭐ 만약 다른 배열을 안 만들어주고 map을 그대로 이용한다면 ??

      →  bfs를 딱 한번 돌면 괜찮지만 벽이 3개 세워지는 경우의 수만큼 bfs를 돌아야하기 때문에 바이러스를 퍼트린 뒤 매번 map을 처음 상태로 되돌려 놓는것은 굉장히 비효율적인 일이다

      → bfs에 들어올때마다 virus 배열을 초기화해주고 map값을 넣어주는게 훨씬 낫다!! 2가 있는 자리도 어차피 확인해야하기 때문에 한번에 두가지 일을 할 수 있게 된다

 

 

3. 0의 개수 확인

	int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (virus[i][j] == 0) {
                    count++;
                }
            }
        }

        answer = Math.max(answer, count);

(bfs 안에서 while문 다음에 나온다)

 

- virus 배열을 돌면서 0을 만나면 count 해준다

- 최종 답은 0의 개수가 "최대"일 때를 구하는 것이므로 현재 answer에 담겨있는 값과 count를 비교하여 더 큰 것을 다시 answer에 저장한다 

 

 

 

 

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

    static int N; // 세로
    static int M; // 가로
    static int[][] map; // 지도
    static int[][] virus; // 바이러스 지도
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int answer = -1;


    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++) {
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //System.out.println(Arrays.deepToString(map));

        dfs(0);
        System.out.println(answer);

    }


    static void dfs(int wall) { // 벽 세우는 경우의 수
        if (wall == 3) {
            bfs(); // 벽이 3개 세워지면 바이러스 퍼지는거 확인
            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(wall + 1);
                    map[i][j] = 0;
                }
            }
        }
    }


    static void bfs() { // 바이러스 퍼지는거 확인
        Deque<int[]> dq = new ArrayDeque<>();
        virus = new int[N][M]; // bfs 새로 들어올때마다 초기화됨

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                virus[i][j] = map[i][j];
                if(virus[i][j] == 2) {
                    dq.addLast(new int[] {i, j});
                }
            }
        }

        while (!dq.isEmpty()) {
            int[] xy = dq.pollFirst();
            int x = xy[0];
            int y = xy[1];

            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];

                if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                    if (virus[nx][ny] == 0) {
                        dq.addLast(new int[]{nx, ny});
                        virus[nx][ny] = 2;
                    }
                }
            }
        }

        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (virus[i][j] == 0) {
                    count++;
                }
            }
        }

        answer = Math.max(answer, count);
    }
}