<Algorithm> 164. 연구소(BJO)

1. 14502번 연구소(BJO)

   사용 알고리즘 : DFS, 완전탐색 

• 예전에 풀었던 문제인데 오랜만에 풀수 있을까 싶어서 다시 풀어보았다. 30분도 안되서 풀고 속도랑 코드량이 많이 줄었다!!

• 궁금해서 BufferedReader랑 Scanner랑 차이가 있을까 싶어서 해봤는데 별로 차이가 없다... n,m이 작은 것도 있지만..

• Scanner 쓴다고 해서 정답이 시간초과가 나는 경우는 없을 것 같다.( Scanner 가 보기에 더 깔끔...)

문제에 대한 접근&생각

1. 벽을 최대 3개 지정할 수 있음 -> 완전탐색!
2. 바이러스는 벽을 제외하고 퍼짐 -> DFS!

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

import java.util.Scanner;   public class Main {     static int n,m;     static int[][] map;     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         /******************************          * DFS를 이용해 벽 쌓는 것을 완전탐색하고          * 바이러스가 퍼지는 경우를 체크해서          * 안전영역의 갯수를 구한다.          *******************************/         n = sc.nextInt();         m = sc.nextInt();         map = new int[n][m];         for(int i = 0; i <n; i++) {             for(int j = 0; j < m; j++) {                 map[i][j] = sc.nextInt();             }         }         count = 0;         solve(0);         System.out.println(count);     }     public static boolean[][] visited;     static int count;     private static void solve(int wall) {         if(wall == 3) {             visited = new boolean[n][m];             for(int i = 0; i <n; i++) {                 for(int j = 0; j < m; j++) {                     if(map[i][j] == 2 && !visited[i][j]) {                             dfs(i, j);                     }                 }             }                          int total = 0;             for(int i = 0; i <n; i++) {                 for(int j = 0; j < m; j++) {                     if(!visited[i][j]&&map[i][j]==0) {                         total++;                     }                 }             }             count = Math.max(count,total);             return;         }                  for(int i = 0; i <n; i++) {             for(int j = 0; j < m; j++) {                 if(map[i][j] == 0) {                     map[i][j] = 1;                     solve(wall+1);                     map[i][j] = 0;                 }             }         }     }     static int[] dx = {0,0,1,-1};     static int[] dy = {-1,1,0,0};     private static void dfs(int x, int y) {                  visited[x][y] = true;                  for(int i = 0; i < 4; i++) {             int nx = x + dx[i];             int ny = y + dy[i];                          if(isBoundary(nx, ny)&&!visited[nx][ny]&&map[nx][ny]==0) {                 dfs(nx, ny);             }         }     }     public static boolean isBoundary(int nx,int ny) {         if(nx < 0 || ny < 0 || nx >= n || ny >= m)             return false;         return true;     } }   Colored by Color Scripter

cs

 

얻은 것

• 7달전 보다 발전했다....