[JAVA] 백준 연구소 - 14502 ( BFS + DFS)

www.acmicpc.net/problem/14502

14502번: 연구소

 

# 벽은 어디다가 설치하는가??

 

반드시 3개만 설치해야한다고 조건에 명시되어 있다.

 

최대 배열의 너비가 8*8  = 64 이므로 여기서 3개를 선택하는 최대 모든 경우의 수는 41644 이다.  

 

완전 탐색으로 3개를 선택해도 무리가 없다.

 

완전탐색이 가능하면 더이상 생각할 필요가 없는 듯하다.

 

벽 3개를 선택하는 로직은 DFS를 선택한다.

 

static void dfs(int idx,int cnt){
        if(idx == total ) {
            if(cnt == 3) {
            // 모든 인덱스 탐색후 3개를 선택한 경우 
            }

            return;
        }

        // idx는 0부터 n*m 까지 증가하며 idx를 (x,y) 좌표로 바꾸는 로직
        int x = idx/m;
        int y = idx%m;

        if(cnt == 3){
            // 끝까지 탐색하지 않았지만 3개를 선택한 경우
        }
        else {
            // 만약 현재 있는 위치가 0이 아니라면 다음으로 넘어간다.
            if (arr[x][y] != 0) dfs(idx + 1, cnt);
            
            // 만약 현재 3개보다 많은 지역을 선택하면 돌아간다.
            else if(cnt > 3) return;
            
            // 현재 지역을 선택하거나 선택하지 않거나 2가지 경우로 재귀 돌린다.
            else {
                arr[x][y] = 1;
                dfs(idx + 1, cnt + 1);
                arr[x][y] = 0;
                dfs(idx + 1, cnt);
            }

        }

    }

 

 

 

# 안전 지대의 개수를 구하는 로직은 BFS 

 

벽 3개를 선택했다면 이제 안전지대가 얼마나 있는지 BFS 를 통해 선택한다.

 

static int bfs(){
        visited = new boolean[n][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
            
                // 모든 배열 탐색중 현재 위치가 바이러스라면
                if(arr[i][j] == 2){
                    // 현재 위치를 방문 체크 한다.
                    visited[i][j] = true;
                    
                    // 큐를 생성하여 BFS 준비 작업
                    Queue<Pair> q = new LinkedList<>();
                    q.add(new Pair(i,j));
                    
                    
                    while(!q.isEmpty()){
                        Pair p  = q.poll();
                        
                        // 현재 위치에서 4가지 방향을 탐색한다.
                        for(int k=0;k<4;k++){
                            int nx = p.x + dx[k];
                            int ny = p.y + dy[k];
                            
                            // 현재 위치가 유효한지 검사한다.
                            if(nx <0 || nx>=n || ny<0 || ny>=m) continue;
                            
                            // 방문한적이 없고 벽이 아니라면? 방문체크한다.
                            if(visited[nx][ny]==false && arr[nx][ny]==0){
                                visited[nx][ny] = true;
                                q.add(new Pair(nx,ny));
                            }

                        }
                    }
                }
            }
        }
        int ret = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 방문한적이 없는데 현재 위치가 0 이라면 안전지대라는 뜻
                if(visited[i][j]==false && arr[i][j]==0){
                    ret++;
                }
            }
        }
        // 안전지대의 개수를 반환한다.
        return ret;
    }

 

 

# 전체 코드

 

import java.util.LinkedList;
import java.util.*;


class Main{

    static int n;
    static int m;
    static int total;
    static int[][] arr;
    static int answer = Integer.MIN_VALUE;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};


    public static void main(String[] args){
        Scanner sc =  new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        total = n*m;

        arr = new int[n][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                arr[i][j] = sc.nextInt();
            }
        }


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

    }

    static void dfs(int idx,int cnt){
        if(idx == total ) {
            if(cnt == 3) {
                int temp = bfs();
                answer = answer < temp ? temp : answer;
            }

            return;
        }

        int x = idx/m;
        int y = idx%m;

        if(cnt == 3){
            int temp = bfs();
            answer = answer < temp ? temp : answer;
        }
        else {
            if (arr[x][y] != 0) dfs(idx + 1, cnt);
            else if(cnt > 3) return;
            else {
                arr[x][y] = 1;
                dfs(idx + 1, cnt + 1);
                arr[x][y] = 0;
                dfs(idx + 1, cnt);
            }

        }

    }

    static int bfs(){
        visited = new boolean[n][m];

        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(arr[i][j] == 2){
                    visited[i][j] = true;
                    Queue<Pair> q = new LinkedList<>();
                    q.add(new Pair(i,j));
                    while(!q.isEmpty()){
                        Pair p  = q.poll();
                        for(int k=0;k<4;k++){
                            int nx = p.x + dx[k];
                            int ny = p.y + dy[k];

                            if(nx <0 || nx>=n || ny<0 || ny>=m) continue;
                            if(visited[nx][ny]==false && arr[nx][ny]==0){
                                visited[nx][ny] = true;
                                q.add(new Pair(nx,ny));
                            }

                        }
                    }
                }
            }
        }
        int ret = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(visited[i][j]==false && arr[i][j]==0){
                    ret++;
                }
            }
        }
        return ret;
    }

    static class Pair{
        int x,y;

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

}