알고리즘 풀이 - 백준 14502(연구소, 그래프(BFS, DFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxM 크기의 지도에 빈 칸, 벽, 바이러스로 이루어져 있을 때, 벽을 3개 놓을 경우 바이러스로 감염되지 않는 빈 칸(안전 영역)의 최대 크기를 구하는 문제

 

 

2. 풀이

 

현재 빈 칸(비 감염, 벽이 아닌 부분) 중 3군데를 고르는 모든 경우를 체크 해야 하는 문제이다.

백트래킹(벽을 세움) + 감염 위치 탐색(BFS 또는 DFS)를 통해 완전 탐색을 수행하는 문제이다.

 

빈 칸에 벽이 3군데 세워질 때까지 백트래킹을 통해 위치 시킨 후 현재 감염된 위치 주위를 모두 감염시킨 뒤 안전 지대 크기를 구하여 그 값이 최대가 되도록 하는 문제이다.

코드로 직접 알아보자.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

① BFS로 해결

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

public class Main{
    static int n, m;
    static int[][] map;
    static ArrayList<Pos> virus;
    static int wall = 3;
    static int safe = 0;
    static int infected = Integer.MAX_VALUE;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 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];
        virus = new ArrayList<>();
        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());
                // 바이러스는 별도의 list에 저장
                if(map[i][j] == 2) {
                    virus.add(new Pos(i, j));
                } else if(map[i][j] == 1){
                    wall++;
                }
            }
        }
        backtrack(0, 0, 0);
        System.out.println(safe);
        
        br.close();
    }
    
    // 백트래킹을 통해 빈 칸에 벽을 최대 3개 놓을 때까지 반복
    // 벽이 3개 놓여지면 BFS를 수행
    private static void backtrack(int i, int j, int wall){
        if(wall > 3) return;
        
        // 벽이 3개 놓여질 때마다 BFS 탐색 수행
        if(wall == 3) {
            bfs();
        }
        for(int y=i; y < n; y++){
            for(int x=0; x < m; x++){
                if(map[y][x] == 0){
                    // 현재 위치에 벽을 놓는다.
                    map[y][x] = 1;
                    
                    backtrack(y, x, wall+1);
                    
                    // 다시 벽을 뺀다.
                    map[y][x] = 0;
                }
            }
        }
    }
    
    // BFS 수행
    private static void bfs(){
        boolean[][] visited = new boolean[n][m];
        Queue<Pos> q = new LinkedList<>();
        
        // 이미 감염된 부분은 Queue에 넣고 탐색 완료로 처리
        for(Pos v : virus){
            q.offer(v);
            visited[v.y][v.x] = true;
        }
        
        int temp = virus.size();
        while(!q.isEmpty()){
            Pos c = q.poll();
            int cy = c.y;
            int cx = c.x;
            
            for(int i=0; i < 4; i++){
                int ny = cy+dy[i];
                int nx = cx+dx[i];
                
                // 범위를 벗어났거나 이미 감염된 경우는 탐색하지 않는다.
                if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
                
                // 만약 빈 칸이라면
                if(map[ny][nx] == 0){
                
                    // 감염시킨다.(Queue에 넣어 다음에 탐색 + 방문 완료 처리)
                    q.offer(new Pos(ny, nx));
                    visited[ny][nx] = true;
                    
                    // 감염된 범위를 추가
                    temp++;
                }
                
                // 기존에 이미 감염된 구역보다 더 많은 구역이 감염됐다면 이번 BFS는 답이 아니므로
                // 바로 반환
                if(temp > infected) return;
            }
        }
        
        // 안전 지대의 크기를 구한다.
        safe = Math.max(safe, n*m - wall - temp);
        
        // 감염된 크기를 갱신
        infected = Math.min(infected, temp);
    }
}

class Pos{
    int y;
    int x;
    public Pos(int y, int x){
        this.y = y;
        this.x = x;
    }
}

 

② DFS로 해결

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;

public class Main{
    static int n, m;
    static int[][] map;
    static boolean[][] visited;
    static ArrayList<Pos> virus;
    static int safe = 0;
    static int[] dy = {-1, 1, 0, 0};
    static int[] dx = {0, 0, -1, 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];
        virus = new ArrayList<>();
        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());
                if(map[i][j] == 2) {
                    virus.add(new Pos(i, j));
                }
            }
        }
        
        // 백트래킹을 통해 벽을 최대 3개 까지 위치 시키고 DFS 수행
        backtrack(0, 0, 0);
        
        // 안전지대 최대 크기를 출력
        System.out.println(safe);
        
        br.close();
    }
    
    // 백트래킹 수행
    private static void backtrack(int i, int j, int wall){
        if(wall > 3) return;
        
        // 벽이 3개 놓여질 때마다 DFS 수행
        if(wall == 3) {
            visited = new boolean[n][m];
            
            // 모든 바이러스 위치에서 DFS 수행하여 감염시킨다.
            for(Pos v : virus){
                dfs(v.y, v.x);
            }
            int cnt = check();
            safe = Math.max(safe, cnt);
        }
        
        // 벽을 3개 위치시킬 때까지 백트래킹 수행
        for(int y=i; y < n; y++){
            for(int x=0; x < m; x++){
                if(map[y][x] == 0){
                    map[y][x] = 1;
                    backtrack(y, x, wall+1);
                    map[y][x] = 0;
                }
            }
        }
    }
    
    private static void dfs(int y, int x){
        for(int i=0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            
            // 범위 벗어났거나 이미 방문 완료된 경우 제외
            if(ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx]) continue;
            if(map[ny][nx] != 0) continue;
            visited[ny][nx] = true;
            dfs(ny, nx);
        }
    }
    
    // 안전지대의 크기를 찾는다.
    private static int check(){
        int cnt = 0;
        for(int i=0; i < n; i++){
            for(int j=0; j < m; j++){
                // 감염되지 않은 경우
                if(map[i][j] == 0 && !visited[i][j]) cnt++;
            }
        }
        return cnt;
    }
}

class Pos{
    int y;
    int x;
    public Pos(int y, int x){
        this.y = y;
        this.x = x;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.