[백준]14502: 연구소 - JAVA

[백준]14502: 연구소

www.acmicpc.net/problem/14502

14502번: 연구소

풀이

조합 + 탐색문제이다.

 

조합을 사용하는 이유는 벽의 위치를 뽑을 때 순서가 상관없기 때문에 조합을 사용했다. 조합을 구현할 때 다음에 뽑을 벽의 위치를 부분이 까다로웠다. 이전의 뽑은 벽의 위치보다 이후의 위치에서 벽을 선택해야 했는데 입력받은 node는 이차원 배열로 되어있어 y값을 어떻게 처리해야 할지 고민이 되었다.

 

처음에는 다음과 같이 구현하였다.

for(int i = x; i < n; i++) {
	for(int j = y; j < m; j++) {
		if(node[i][j] == 0) {
			node[i][j] = 1;	
			combination(idx + 1, i, j);
			node[i][j] = 0;
		}
	}
}

이렇게 구현하면 문제점이 i값이 증가해도 j는 항상 y보다 큰 부분만 확인한다. i값이 증가하면 j는 다시 0부터 탐색해야 하는데 말이다. 이러한 문제점을 해결하기 i값만을 사용해서 확인할 수 있도록 하였다.

 

예를 들어 n이 4이고, m이 6일때 각 노드의 인덱스를 다음과 같이 생각해 줄 것이다.

0	1	2	3	4	5
6	7	8	9	10	11
12	13	14	15	16	17
18	19	20	21	22	23

이런식으로 하고 i값의 범위를 n * m = 24 로 둘 것이다. 

 

그럼 위의 값을 이차원 배열의 인덱스로 변환해주는 과정이 필요하다.

가장 왼쪽, 첫 번째 행을 보면 아래와 같다.

i값	원래 인덱스
0	0
6	1
12	2
18	3

i값이 다음과 같을때 원래 2차원 배열에서의 첫 번째 인덱스가 각각 어떤 값을 의미하는지이다. 이를 보면 규칙이 보인다. 즉, i값에서 m(6)으로 나눈 몫이 원래의 첫 번째 인덱스가 된다. 이는 다른 행을 확인해보아도 똑같다.

 

다음으로 가장 아래쪽 열을 보면 아래와 같다.

i값	18	19	20	21	22	23
원래 인덱스	0	1	2	3	4	5

이번에는 i값이 다음과 같을때 i값을 m(6)으로 나눈 나머지가 원래 인덱스가 된다. 즉 두 번째 인덱스로 변환해 줄 수 있다.

 

이제 다음과 같이 변경해주면 조합으로 벽의 위치 뽑을 수 있다.

for(int i = x; i < n * m; i++) {
    int nx = i / m;
    int ny = i % m;
    if(node[nx][ny] == 0) {
        node[nx][ny] = 1; //벽 세우기
        combination(idx + 1, i + 1);//i + 1을 해주는 이유는 다음에 뽑을 숫자가 i보다 커야하기 때문이다.
        node[nx][ny] = 0; //벽 허물기
     }
}

 

벽의 위치를 다 뽑고 난 후에는 dfs로 바이러스를 퍼트리고, 다 퍼트린 후 안전 영역(node[i][j] == 0)의 개수를 세서 그 중에 최대값을 반환해 주면 된다!

 

코드

import java.util.*;
 
public class Main {    
 
    static int n, m;
    static int[][] node;
    static int max = 0;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    
    public static void main(String[] args) throws Exception {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        
        node = new int[n][m];
        for(int i = 0; i< n; i++) {
            for(int j = 0; j < m; j++) {
                node[i][j] = scan.nextInt();
            }
        }
 
        combination(0, 0);
        
        System.out.println(max);
    }
    //노드를 확인하여 바이러스가 존재하면 DFS를 사용해 바이러스를 퍼트린다.
    public static void virus(int[][] copy) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(copy[i][j] == 2) dfs(copy, i, j);
            }
        }
    }
    //DFS탐색을 통해 바이러스를 퍼트린다.
    public static void dfs(int[][] copy, int x, int y) {
        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                if(copy[nx][ny] == 0) {
                    copy[nx][ny] = 2;
                    dfs(copy, nx, ny);
                }
            }
        }
    }
    //안전 영영의 수를 센다.
    public static int calArea(int[][] copy) {
        int count = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(copy[i][j] == 0) count++;
            }
        }
        return count;
    }
    //벽의 위치를 조합으로 뽑는다.
    public static void combination(int idx, int x) {
        if(idx == 3) {
            int[][] copy = new int[n][m];
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    copy[i][j] = node[i][j];
                }
            }
            virus(copy); //바이러스가 퍼진다.
            max = Math.max(max, calArea(copy));
            return;
        }
        
        for(int i = x; i < n * m; i++) {
            int nx = i / m;
            int ny = i % m;
            if(node[nx][ny] == 0) {
                node[nx][ny] = 1; //벽 세우기
                combination(idx + 1, i + 1);//i + 1을 해주는 이유는 다음에 뽑을 숫자가 i보다 커야하기 때문이다.
                node[nx][ny] = 0; //벽 허물기
            }
        }
    }
}