백준 - 14502 연구소

DFS의 개념이 필요한 문제였습니다.

다음에 다시 한번 보도록 해야겠습니다.

package com.company;

import java.util.Scanner;

public class boj14502version2 {

    static int N, M,totalCNT;
    static int[][] map, visited;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N][M];
        visited = new int[N][M];


        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                map[i][j] = sc.nextInt();
            }
        }

        for(int i=0; i<N*M; i++){
                    int row = i/M;
                    int col = i%M;
                    if(map[row][col] == 0){
                        map[row][col] = 1;
                        DFS(i, 1);
                map[row][col] = 0;
            }
        }

        System.out.println(totalCNT);
    }

    static void DFS(int v, int cnt){
        int row = v/M;
        int col = v%M;

        if(cnt == 3){
            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    visited[i][j] = map[i][j];
                }
            }

            for(int i=0; i<N; i++){
                for(int j=0; j<M; j++){
                    if(visited[i][j] == 2){
                        spreadVirus(i,j);
                    }
                }
            }
            safetyArea();
        } else {
            for(int i=v+1; i<N*M; i++){
                int row2 = i/M;
                int col2 = i%M;
                if(map[row2][col2] == 0){
                    map[row2][col2] = 1;
                    DFS(i, cnt+1);
                }
            }
        }
        map[row][col] = 0;
    }

    static void spreadVirus(int row, int col) {
        for(int i=0; i<4; i++) {
            int nextRow = dx[i]+row;
            int nextCol = dy[i]+col;
            if(nextRow>=0 && nextRow<N && nextCol>=0 && nextCol<M) {
                if(visited[nextRow][nextCol]==0) {
                    visited[nextRow][nextCol]=2;
                    spreadVirus(nextRow, nextCol);
                }
            }
        }
    }

    //안정 영역 크기 구하기
    static void safetyArea() {
        int cnt=0;
        for(int i=0; i<N; i++) {
            for(int j=0; j<M; j++) {
                if(visited[i][j]==0) {
                    cnt++;
                }
            }
        }
        if(totalCNT<cnt) {
            totalCNT = cnt;
        }
    }
}