문제 14502 연구소(성공)

• 짤린 문제 내용 : 백준14502
  

소스코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class virus{
    int x;
    int y;
    public virus(int x, int y ){
        this.x = x;
        this.y = y;
    }
}
public class boj14502 {
    static int n;
    static int m;
    static int[][] a = new int[10][10];
    static int[][] b = new int[10][10];
    static int[][] dirs = {{-1,0},{1,0}, {0,1},{0,-1}};
    public static void dfs(int x, int y){
        for(int[] dir : dirs){
            int nx = x + dir[0];
            int ny = y + dir[1];
            if(nx>=0 &&ny>=0&& nx<n&&ny<m){
                if(b[nx][ny] ==0){
                    b[nx][ny] =2;
                    dfs(nx,ny);
                }
            }
        }
    }
    public static int dfs(){
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                b[i][j] = a[i][j];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(i,j);
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(b[i][j] ==0) cnt++;
            }
        }
        return cnt;
    }
    public static int bfs() {
        Queue<virus> qu = new LinkedList<>();
        b = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                b[i][j] = a[i][j];
                if(a[i][j] ==2){
                    qu.add(new virus(i,j));
                }
            }
        }
        while(!qu.isEmpty()){
            virus q = qu.poll();
            int x = q.x;
            int y = q.y;
            for(int[] dir : dirs){
                int nx = x + dir[0];
                int ny = y + dir[1];
                if(nx>=0 &&ny>=0&& nx<n&&ny<m){
                    if(b[nx][ny] == 0){
                        b[nx][ny] = 2;
                        qu.add(new virus(nx,ny));
                    }
                }
            }
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(b[i][j] == 0) cnt++;
            }
        }
        return cnt;
    }
    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());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int result = 0;
        for (int x1 = 0; x1 < n; x1++) {
            for (int y1 = 0; y1 < m; y1++) {
                if(a[x1][y1] != 0) continue;
                for (int x2 = 0; x2 < n; x2++) {
                    for (int y2 = 0; y2 < m; y2++) {
                        if(a[x2][y2] != 0) continue;
                        for (int x3 = 0; x3 < n; x3++) {
                            for (int y3 = 0; y3 < m; y3++) {
                                if(a[x3][y3] != 0) continue;
                                if(x1 == x2 && y1 == y2) continue;
                                if(x1 == x3 && y1 == y3) continue;
                                if(x2 == x3 && y2 == y3) continue;
                                a[x1][y1] = 1; a[x2][y2] = 1; a[x3][y3] = 1;
                                int cur = bfs();
                                result = Math.max(result, cur);
                                a[x1][y1] = 0; a[x2][y2] = 0; a[x3][y3] = 0;
                            }
                        }
                    }
                }
            }
        }
        System.out.println(result);
    }
}

문제 접근

1. 문제 행열에서 0은 빈 칸, 1은 벽, 2는 바이러스라고 하였고, 바이러스는 상하좌우로 벽을 제외하고 퍼진다고 하였다.
2. 벽 3개를 설치하고 바이러스를 확산 시켰을 때 남은 0의 값의 개수 중 최대값을 출력하는 문제다.
3. 결국 모든 위치를 다 지나므로 bfs로도 풀 수 있고, dfs로도 풀 수 있는 문제이다.
4. 6겹의 반복문으로 벽 3가지의 좌표를 잡는데, 좌표들이 0이 아니거나, 아예 같은 좌표를 나타내는 벽이 있으면 continue를 한다.
5. 이 조건을 만족하면 bfs or dfs를 돌고, 최대값을 Math.max로 받아 출력한다.
   BFS와 DFS 정리 velog

문제 핵심

• 문제 해결 방안으로 적절한 탐색 방법을 선택 했는지!
• 구현에 문제가 없었는지