5653. [모의 SW 역량테스트] 줄기세포배양
문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRJ8EKe48DFAUo
풀면서도 정말 풀기 싫은 문제였다.
머리가 잘 돌아가고, 온전히 집중할 수 있을 때 풀어야 될 문제.
이런 문제가 시험에 나온다면 시간 다 잡아먹을 것 같다.
따로 설명할 게 없다.
그냥 문제에 나온 지시사항을 충실히 코드로 옮기면 됨.
주의할 점은,
배열을 입력받은 N과 M으로 초기화할 것이 아니라
애초부터 크게 잡아둬야 한다는 점.
나는 [700][700]으로 잡았다.
더보기
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Solution_sw_5653_줄기세포배양 {
static final int DEAD = 0, DISABLED = 1, ACTIVE = 2, LENGTH = 700;
static int T, N, M, K;
static Cell[][] map;
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { -1, 0, 1, 0 };
static ArrayList<Cell> activedCells, disabledCells, deadCells;
static int midY, midX;
static class Cell {
int y;
int x;
int life = 0;
int status = DISABLED;
int genTime;
int beginActiveTime;
public Cell() {
}
public Cell(int y, int x, int life, int status, int genTime) {
super();
this.y = y;
this.x = x;
this.life = life;
this.status = status;
this.genTime = genTime;
}
@Override
public String toString() {
return "Cell [y=" + y + ", x=" + x + ", life=" + life + ", status=" + status + ", genTime=" + genTime
+ ", beginActiveTime=" + beginActiveTime + "]";
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
T = Integer.parseInt(br.readLine());
for (int t = 1; t <= T; t++) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); // N : 세로
M = Integer.parseInt(st.nextToken()); // M : 가로
K = Integer.parseInt(st.nextToken()); // K : 배양시간
// map 배열 초기화
map = new Cell[LENGTH][];
for (int i = 0; i < LENGTH; i++) {
map[i] = new Cell[LENGTH];
}
for (int i = 0; i < LENGTH; i++) {
for (int j = 0; j < LENGTH; j++) {
map[i][j] = new Cell();
}
}
// 자료구조 초기화
activedCells = new ArrayList<>();
disabledCells = new ArrayList<>();
deadCells = new ArrayList<>();
Queue<Cell> queue = new LinkedList<>();
// map 입력
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
int value = Integer.parseInt(st.nextToken());
map[LENGTH / 2 + i][LENGTH / 2 + j] = new Cell(LENGTH / 2 + i, LENGTH / 2 + j, value, DISABLED, 0);
if (map[LENGTH / 2 + i][LENGTH / 2 + j].life > 0)
disabledCells.add(map[LENGTH / 2 + i][LENGTH / 2 + j]);
}
}
// K 시간이 될 때 까지, 알고리즘 반복
for (int hour = 0; hour <= K; hour++) {
// X시간동안 활성 ( bfs 번식 )
queue.addAll(activedCells);
int size = queue.size();
for (int i = 0; i < size; i++) {
Cell cell = queue.poll();
for (int d = 0; d < 4; d++) {
int ny = cell.y + dy[d];
int nx = cell.x + dx[d];
if (map[ny][nx].life == 0 && map[ny][nx].status == DISABLED) {
map[ny][nx] = new Cell(ny, nx, cell.life, DISABLED, hour);
disabledCells.add(map[ny][nx]);
}
}
}
// 비활성화 된 Cell 중, 활성화 될 Cell이 있으면 activeCells에 넣음
ArrayList<Cell> tempCells = new ArrayList<>();
tempCells.addAll(disabledCells);
for (Cell cell : tempCells) {
if (cell.life == hour - cell.genTime && cell.status == DISABLED) {
disabledCells.remove(cell);
cell.status = ACTIVE;
cell.beginActiveTime = hour;
activedCells.add(cell);
}
}
// 활성 후, X시간 뒤 사망
tempCells.addAll(activedCells);
for (Cell cell : tempCells) {
if (cell.beginActiveTime + cell.life == hour) {
activedCells.remove(cell);
cell.status = DEAD;
deadCells.add(cell);
}
}
}
sb.append("#" + t + " " + (activedCells.size() + disabledCells.size()) + "\n");
}
System.out.println(sb.toString());
}
}
|
cs |
'알고리즘' 카테고리의 다른 글
| [Boj] S1 1041 주사위 (1) | 2020.04.19 |
|---|---|
| [SWEA] 1949. [모의 SW 역량테스트] 등산로 조성 (0) | 2020.04.19 |
| [SWEA] 2117. [모의 SW 역량테스트] 홈 방범 서비스 (0) | 2020.04.19 |
| [Boj] S1 2812 크게 만들기 (0) | 2020.04.14 |
| [SWEA] 5658. [모의 SW 역량테스트] 보물상자 비밀번호 (1) | 2020.04.13 |