BOJ] 14502. 연구소
https://www.acmicpc.net/problem/14502
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 |