[BOJ_14502 | DFS] 연구소

풀이

설마 이렇게 벽을 3개 세울 수 있는 모든 경우의 수를 다 확인해 봐야하는 건가? 라고 생각하면서 문제를 풀었던 것 같다.

하나의 벽을 세우기 위해서 행과 열을 세는 n*m반복문을 세워야하고 벽을 3개 세워야 하므로

벽을 세우는 데만 반복문을 6개를 사용했고, 또 DFS를 위해 반복문을 두개 또 집어넣어야 해서

결과적으로는 반복문을 8개나 집어넣는 어마무시한 일이 발생해버렸다. 

하지만 애초에 n<=8, m<=8인 굉장히 작은 데이터셋을 다루기 때문에 

8^8 = 2^24 = 약 10,000,000번의 연산 정도밖에 수행하지 않아 시간초과의 염려는 없었던 것 같다.

그외의 문제 해결은 여느 DFS와 크게 다르지 않았던 것 같다.

반복문을 돌면서 2인 지점을 찾아 상하좌우가 0이면 2로 바꾸고 그 위치에서 다시 탐색하는 식이다.

모든 탐색이 끝나면 0의 개수를 세어 Max와 비교하여 Max를 갱신해 주면 된다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_14502 {
 
    static int n, m, cnt, max;
    static int[][] map, saveMap;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m]; cnt = 0; max = -1;
        saveMap = new int[n][m];
 
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
                saveMap[i][j] = map[i][j];
            }
        }
        //insert wall
        for(int i1=0;i1<n;i1++){
            for(int j1=0;j1<m;j1++){
                for(int i2=i1;i2<n;i2++){
                    for(int j2=0;j2<m;j2++){
                        for(int i3=i2;i3<n;i3++){
                            for(int j3=0;j3<m;j3++){
                                if(map[i1][j1] == 0 && map[i2][j2] == 0 && map[i3][j3] == 0 &&
                                        !(i1==i2 && j1==j2) && !(i2==i3 && j2==j3) && !(i1==i3 && j1==j3)){
                                    map[i1][j1]=1; map[i2][j2]=1; map[i3][j3] = 1;
                                    cnt = 0;
                                    for(int i = 0;i<n;i++){
                                        for(int j=0;j<m;j++){
                                            if(map[i][j] == 2)dfs(i, j);
                                        }
                                    }
                                    for(int i=0;i<n;i++){
                                        for(int j=0;j<m;j++){
                                            if(map[i][j] == 0)cnt++;
                                        }
                                    }if(cnt>max) {max = cnt;}
                                    saveMap();
                                }
                            }
                        }
                    }
                }
            }
        }
        bw.write(max+"\n");
        bw.flush();
        bw.close();
    }
    public static void dfs(int x, int y){
        for(int i=0;i<4;i++){
            if(isValid(x+dx[i], y+dy[i]) && map[x+dx[i]][y+dy[i]] == 0){
                map[x+dx[i]][y+dy[i]]=2; dfs(x+dx[i], y+dy[i]);
            }
        }
    }
    public static boolean isValid(int x, int y){
        if(x>=0 && x<n && y>=0 && y<m) return true;
        return false;
    }
    public static void print(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                System.out.print(map[i][j]+" ");
            }System.out.println();
        }System.out.println();
    }
    public static void saveMap(){
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                map[i][j] = saveMap[i][j];
            }
        }
    }
}