백준 14502 연구소 (자바)

<문제>

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

14502번: 연구소

 

<풀이>

(난이도가 어려운 문제일수록 차분하게 필요한 기능이 무엇인지 생각을 하고 해당 기능을 하나하나 구현을 해야 한다)

이 문제를 풀려면 크게 2가지 기능이 있어야 한다. 첫 번째로 3개의 벽을 두는 모든 경우의 수를 구하는 기능, 두 번째로 3개의 벽을 뒀을때 해당 경우에서 바이러스를 퍼지게 하는 기능이다.

 

첫 번째 기능은 3개의 좌표를 고르는 경우를 구해야 하기 때문에 모든 경우의 수를 구한다 -> dfs 탐색으로 해결한다라고 생각을 했다.

두 번째 같은 경우에는 바이러스를 퍼지게 한다 -> 바리어스의 위치를 큐에 넣고 하나씩 꺼내면서 상하좌우로 바이러스를 퍼지게 하고 퍼진 위치의 바이러스를 큐에 다시 넣는다. -> bfs에서 큐가 사용되니 bfs를 이용한다.

 

이렇게 문제에 접근했다.

 

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 result = 0;
    public static boolean[][] visited;

    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());
            }
        }

        dfs(0);
        System.out.println(result);
    }

    public static void dfs(int cnt) {

        if(cnt == 3) {
            bfs(); // 벽 3개를 뒀을때 바이러스를 퍼트리다.
        }
        else {
            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++) { // 바이러스 시작 위치를 다 queue에 넣기
            for(int j = 0; j < m; j++) {
                if(map[i][j] == 2)
                queue.add(new int[] {i,j});
            }
        }

        visited = new boolean[n][m];

        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(!visited[nextX][nextY] && map[nextX][nextY] == 0) {
                    visited[nextX][nextY] = true;
                    queue.add(new int[] {nextX,nextY}); // 바이러스가 퍼진 구역이면 다시 큐에 넣어서 해당 위치에서 또 퍼지게 하기
                }
            }
        }
        checkSafeArea();
    }

    public static void checkSafeArea() { // 안전구역 개수 확인
        int safeAreaCount = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!visited[i][j] && map[i][j] == 0) {
                    safeAreaCount++;
                }
            }
        }
        result = Math.max(safeAreaCount, result);
    }



}