[백준 17142] 연구소3 (Java, BFS)
Algorithm/백준(BOJ)

[백준 17142] 연구소3 (Java, BFS)

반응형

 

 

[백준 17142] 연구소3 (Java, BFS)

 

문제 출처 : 링크

 

17142번: 연구소 3

인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 모두 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는

www.acmicpc.net

 

올해 상반기 삼성전자 역량테스트 문제다.

 

예전에 나온 삼성 기출 '연구소'에서 조건만 좀 더 추가된 문제

 

3가지 조건만 잘 기억하고 풀어보자

 

1. '2'인 바이러스 위치에서 M개만 고르기 ( 조합 )

2. 벽을 제외하고 최소로 이동할 수 있는 값 배열에 저장하기

3. 비활성 바이러스가 활성 바이러스를 만나면 활성으로 변경

 

벽이나 이동하지 못하는 곳을 문제 예시처럼 '*'을 이용하거나 '-'을 쓰기 위해 char형 배열을 만들면 되겠지만, 그냥 int형으로 풀었다.

 

벽인 곳은 -1로 만들고, 비활성 바이러스는 -9, 활성 바이러스는 -2로 만들어 진행했다.

 

BFS를 통해 활성 바이러스인 곳들을 모두 돌린 후, 각 배열의 위치에 최소 이동거리를 갱신해나간다. 마지막에 이동한 거리 중 최대값을 저장하고, 조합을 돌리면서 이 최대값이 가장 작은걸 뽑아내면 된다.

 

만약 0인 값이 존재한다면, 바이러스가 퍼진 후에도 갈 수 없는 곳이 있다는 뜻이다. 모든 조합의 경우에서 이런 상황이 발생하면, -1을 출력해주면 된다.

 

백준의 마지막 테스트케이스는 아예 빈칸 0이 없고 바이러스와 벽으로만 구성된 경우다.

이런 상황은 한번에 모두 퍼지면서 정답이 0이 되야한다. 이것만 따로 체크해주면 모든 경우의 수에 대한 값을 나타낼 수 있다.

 

 

 

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main_17142_연구소3 {
 
    public static class Virus {
        int y;
        int x;
        int val;
        
        Virus(int y, int x, int val) {
            this.y = y;
            this.x = x;
            this.val = val;
        }
    }
    
    public static int N, M;
    public static int[][] map;
    public static int[][] copy;
    public static boolean[][] visited;
    
    public static int[] dy = {-1,1,0,0}; // 상하좌우
    public static int[] dx = {0,0,-1,1};
    public static ArrayList<Virus> list;
    
    public static int[] set;
    
    public static int result;
    public static int max;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String[] str = br.readLine().split(" ");
        
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        
        map = new int[N][N];
        list = new ArrayList<>();
        
        for (int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(str[j]);
                if(map[i][j] == 2) { // 바이러스 위치
                    list.add(new Virus(i,j,0));
                }
            }
        }
        
        set = new int[M];
        result = Integer.MAX_VALUE;
        
        comb(0,0);
        
        if(result != Integer.MAX_VALUE)
            System.out.println(result);
        else
            System.out.println(-1);
    }
 
    
    public static void comb(int len, int k) {
        
        if(len == M) {
            copy = new int[N][N];
            
            loop : for (int i = 0; i < list.size(); i++) {
                
                for (int j = 0; j < set.length; j++) {
                    if(i == set[j])
                        continue loop;
                }
                
                Virus v = list.get(i);
                
                copy[v.y][v.x] = -9// 비활성 바이러스는 -9
            }
            
            for (int i = 0; i < copy.length; i++) {
                for (int j = 0; j < copy.length; j++) {
                    if(map[i][j] == 1) {
                        copy[i][j] = -1// 벽은 -1로 초기화
                    }
                }
            }
            
            for (int i = 0; i < set.length; i++) {
                Virus v = list.get(set[i]);
                
                copy[v.y][v.x] = -2;
            }
            
            for (int s = 0; s < set.length; s++) { // 활성화 바이러스부터 확장 시작
                
                Queue<Virus> q = new LinkedList<>();
                
                visited = new boolean[N][N];
                
                Virus v = list.get(set[s]);
                q.add(v);
                visited[v.y][v.x] = true;
                
                while(!q.isEmpty()) {
                    
                    Virus v1 = q.poll();
                    int val = v1.val;
                    
                    for (int i = 0; i < 4; i++) {
                        
                        int ny = v1.y + dy[i];
                        int nx = v1.x + dx[i];
                        
                        if(ny < 0 || nx < 0 || ny >= N || nx >= N || copy[ny][nx] == -1 || copy[ny][nx] == -2 || visited[ny][nx]) continue;
                        
                        if(copy[ny][nx] == -9) {
                            q.add(new Virus(ny,nx, val+1));
                            visited[ny][nx] = true;
                            continue;
                        }
                        
                        visited[ny][nx] = true;
                        q.add(new Virus(ny,nx, val+1));
                        
                        if(copy[ny][nx] == 0)
                            copy[ny][nx] = val + 1;
                        else {
                            if(copy[ny][nx] > val+1)
                                copy[ny][nx] = val + 1;
                        }
                        
                    }
                    
                }
            }
            
            max = Integer.MIN_VALUE;
            
            for (int i = 0; i < copy.length; i++) {
                for (int j = 0; j < copy.length; j++) {
                    if(copy[i][j] == 0// 갈수 없는 곳
                        return;
                }
            }
            
            
            for (int i = 0; i < copy.length; i++) {
                for (int j = 0; j < copy.length; j++) {
                    if(copy[i][j] < 0continue;
                    if(max < copy[i][j]) max = copy[i][j];
                }
            }
            
            /*for (int i = 0; i < copy.length; i++) {
                for (int j = 0; j < copy.length; j++) {
                    System.out.print(copy[i][j] + " ");
                }
                System.out.println();
            }
            System.out.println();*/
            
            boolean chk = false;
            loop : for (int i = 0; i < copy.length; i++) {
                for (int j = 0; j < copy.length; j++) {
                    if(copy[i][j] > 0){
                        chk = true;
                        break loop;
                    }
                }
            }
            
            if(!chk) {
                result = 0;
            }
            
            else {
                if(result > max)
                    result = max;
            }
            return;
        }
        
        if(k == list.size()) return;
        
        set[len] = k;
        comb(len+1, k+1);
        comb(len, k+1);
    }
}
 
cs
반응형