Algorithm/BOJ

BOJ] 14502. 연구소

BOJ] 14502. 연구소

https://www.acmicpc.net/problem/14502

 

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.  일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다.

www.acmicpc.net

2017년 SW역량테스트 기출문제

풀었던 문제지만, 떠올릴 겸 다시 풀어보았다.
생각보다 막힌 부분이 있었지만 알고리즘을 배우고 나서 다시 보니 느낌이 다르다.

브루트포스 + DFS의 형태의 문제로 해석하여 풀었다.
특히 이 문제를 통해서 알고가야 할 것은
'2차원 배열에서의 조합' 과 '벽을 세우고 다시 원상복귀 시키는 행위'이다. 
이것만 잘 고려했다면, 쉬운 문제겠지만 난 이게 어려웠었다.

연구소 문제 시리즈는 여러모로 배울 점이 많은 문제들이다.( 연구소3도 많이 배웠다.)
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import java.util.ArrayList;
import java.util.Scanner;
 
public class boj14502_연구소 {
 
    static class POS {
        int r;
        int c;
 
        public POS(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
 
    static int R;
    static int C;
    static int AREA;
 
    static int[][] map;
    static int[][] copy;
 
    static ArrayList<POS> VirusList = new ArrayList<POS>();
 
    static int[] dr = {-1,1,0,0};
    static int[] dc = {0,0,-1,1};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        R = sc.nextInt();
        C = sc.nextInt();
        map = new int[R][C];
        copy = new int[R][C];
        
        // 초기 연구소 상태 입력 및 모든 바이러스 위치 저장 
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                map[i][j] = sc.nextInt();
                if(map[i][j]==2)
                    VirusList.add(new POS(i,j));
            }
        }
        setWall(0,0);
        System.out.println(AREA);
    }
 
    
    static void setWall(int start, int depth) {
        //벽을 모두 세운 경우 
        if(depth==3) {
            // 바이러스를 퍼뜨려 볼 벽을 복사
            copyMap();
            
            // 바이러스 퍼뜨리기
            for(POS p : VirusList) {
                // dfs 
                SpreadVirus(p.r, p.c);
            }
            
            // 안전지역 카운팅하기
            // 최대값과 비교하기 
            AREA = Math.max(AREA, SafeArea());
            return;
        }
        
        //2차원 배열에서의 조합.
        for(int i=start; i<R*C; i++) {
            int r = i/C;
            int c = i%C;
            
            //초기 지도에서 빈 공간이었다면.
            if(map[r][c]==0) {
                //벽을 세워본다.
                map[r][c]=1;
                setWall(i+1, depth+1);
                //원상복귀 
                map[r][c]=0;
            }
        }
    }
 
 
    static void SpreadVirus(int r, int c) {
        for(int d=0; d<4; d++) {
            int nr = r + dr[d];
            int nc = c + dc[d];
            
            // 배열범위 확인 
            if(nr<0 || nc<0 || nr >= R || nc >= C) continue;
            
            // 빈 공간이라면,바이러스 전파.
            if(copy[nr][nc]==0) {
                copy[nr][nc]=2;
                SpreadVirus(nr, nc);
            }
        }
    }
    
    static int SafeArea() {
        int total =0;
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                if(copy[i][j]==0)
                    total++;
            }
        }
        return total; 
    }
    
    
    
    static void copyMap() {
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                copy[i][j] = map[i][j];
            }
        }
    }// end copyMap method
}
 
cs

'Algorithm > BOJ' 카테고리의 다른 글

BOJ] 2805. 나무 자르기  (0) 2019.10.05
BOJ] 4179. 불!  (0) 2019.10.05
BOJ] 16283. Farm  (0) 2019.10.01
BOJ] 2579. 계단오르기  (0) 2019.09.25
BOJ] 1003. 피보나치 함수  (0) 2019.09.24