[백준]JAVA - 14502번: 연구소

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

14502번: 연구소

풀이

이번 문제는 bfs와 dfs를 동시에 사용하는 문제로 3개의 벽을 세워서 바이러스로 부터 안전한 구역을 최대한 넓게 만들어야한다.

 

우선 임의로 중복되지 않은 3개의 벽을 계속 세워야하므로 dfs를 이용한다.

벽을 세우고, 다시 복구를 반복하면서 벽 3개가 완성되면 bfs를 돌리면 된다.

public 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;
            }
        }
    }
}

벽 3개가 되었을 때 bfs로 들어가면 map을 copyMap 배열에 그대로 복사 후에 탐색한다. 다른 배열을 새로 만들어서 탐색한 이유는 bfs 탐색을 진행하면서 배열을 건드려버리면 문제가 생기기 때문이다.

 

위의 내용을 반복하면서 최대 몇 개의 안전 구역이 생기는지를 찾으면 된다.

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main {
    static int N, M;
    static int[][] map;
	
    static int[] x = {-1, 0, 1, 0};
    static int[] y = {0, -1, 0, 1};
	
    static int result;
	
    public static class Position {
        int x;
        int y;
		
        public Position (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
	
    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 wall) {
        if (wall == 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(wall+1);
                    map[i][j] = 0;
                }
            }
        }
    }
	
    public static void bfs() {
        int max = 0;
        int[][] copyMap = new int[N][M];
        boolean[][] visited = new boolean[N][M];
		
        Queue<Position> q = new LinkedList<>();
		
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                copyMap[i][j] = map[i][j];
				
                if (copyMap[i][j] == 2) {
                    visited[i][j] = true;
                    q.add(new Position(i, j));
                }
            }
        }
		
        while (!q.isEmpty()) {
            Position now = q.poll();
			
            for (int i=0; i<4; i++) {
                int dx = now.x + x[i];
                int dy = now.y + y[i];
				
                if (dx < 0 || dx >= N || dy < 0 || dy >= M || copyMap[dx][dy] == 1 || visited[dx][dy]) continue;
				
                copyMap[dx][dy] = 2;
                visited[dx][dy] = true;
                q.add(new Position(dx, dy));
            }
        }
		
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (copyMap[i][j] == 0) {
                    max++;
                }
            }
        }
		
        result = Math.max(max, result);
    }
}