백준 14502번 연구소

문제 링크 : https://www.acmicpc.net/problem/14502

브루트포스 문제이다. (참고로 삼성 기출 문제이다.)

완전탐색으로 벽을 세우고 그래프를 탐색하며 바이러스를 퍼트린 후 안전영역의 크기를 구하는 방식으로 풀 수 있다.

처음에 코드를 짠 후에 실행을 해보는데 이클립스에서 돌아가는데도 너무 오래 걸리길래

뭐가 문제일까 생각 하다가 반목문을 2개 줄일 방법을 생각했다.

근데 아무리 생각해봐도 반복 두개 더 줄인다고 나아질 속도가 아니라서 코드를 다시보니 바보같이 재귀호출하며 벽을 3개 세운후에 return을 하지 않고 있었다.

리턴문만 추가 하고 돌려보니 바로 돌아가길래 제출해보니 맞았습니다를 받았다.

맞았기때문에 반복문 2개는 그냥 줄이지 않기로 했다...

그래프를 탐색할땐 bfs를 사용하였다. 완전탐색을 하며 이미 재귀호출을 하고있는데 그 안에서 또 dfs를 사용하여 재귀호츨을 하면 혹시 메모리가 부족할까 싶어서 큐를 사용하는 bfs를 이용하였다.

아래는 소스코드이다.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class Main {
    static int n, m, maxCount;
    static int[][] map;
    static int[][] tmp;
    static boolean[][] visited;
    static int[] dy = { 0, 0, -1, 1 };
    static int[] dx = { -1, 1, 0, 0 };
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        tmp = new int[n][m];
        maxCount = 0;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                map[i][j] = sc.nextInt();
            }
        }    
        
        select(0, -1, 3);
        System.out.println(maxCount);
    }
    
    
    public static void select(int y, int x, int toPick) {
        if(toPick==0) {
            visited = new boolean[n][m];
            bfs();
            int count = 0;
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(tmp[i][j]==0) count++;
                }
            }
            maxCount = Math.max(count, maxCount);
            return;
        }
        
        if(x+1<m) x+=1;
        else {
            if(y+1<n) {
                y+=1;
                x=0;
            } else return;
        }
        
        for(int i=y; i<n; i++) {
            for(int j=x; j<m; j++) {
                if(map[i][j]==1 || map[i][j]==2) continue;
                map[i][j] = 1;
                select(i, j, toPick-1);
                map[i][j] = 0;
            }
            x = 0;
        }
    }
    
    public static void bfs() {
        for(int i=0; i<map.length; i++) {
            System.arraycopy(map[i], 0, tmp[i], 0, map[i].length);
        }
        Queue<Point> q = new LinkedList<Point>();
 
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                if(tmp[i][j]==2 && visited[i][j]==false) {
                    visited[i][j] = true;
                    q.offer(new Point(i, j));
                    
                    while(!q.isEmpty()) {
                        Point current = q.poll();
                        for(int k=0; k<4; k++) {
                            int ny = current.y + dy[k];
                            int nx = current.x + dx[k];
                            if(ny<0 || nx<0 || ny>=n || nx>=m) continue;
                            if(tmp[ny][nx]==1 || visited[ny][nx]==true) continue;
                            
                            visited[ny][nx] = true;
                            tmp[ny][nx] = 2;
                            q.offer(new Point(ny, nx));
                        }
                    }
                }
            }
        }
    }
}
 
class Point {
    int y, x;
    
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
}