[모의 SW 역량 테스트] 미생물 격리 (우선순위 큐)
1. 핵심 개념 및 근거
필요한 개념 및 자료구조
- 시뮬레이션: M시간 동안 정해진 규칙에 따라 미생물의 상태를 변화시켜야 합니다.
- 우선 순위 큐: 미생물 수가 많은 순서대로 처리하여, 같은 칸에 모일 때
가장 큰 군집을 기준으로 방향을 결정하기 위함입니 - 2차원 배열: 특정 시간에 미생물이 어디로 이동했는지 체크하고 병합하기 위한 용도입니다.
선택 근거 및 제약사항
- 병합 조건: “여러 개의 군집이 한 셀에 모이는 경우 미생물 수가 가장 많은 군집의 이동 방향을 가진다.”
- 이 조건 때문에 내림차순 정렬이 필수적입니다. 큰 놈이 먼저 가서 깃발을 꽂으면, 뒤에 오는 작은 놈들은 방향 신경 쓸 필요 없이 흡수만 됩니다.
- 시간 복잡도:
- M번 반복하며, 매번 K개의 미생물을 처리합니다.
- PQ 정렬에 O(KlogK), 이동 처리에 O(K), 맵 초기화에 O(N^2)이 소요됩니다.
- 총합: O(M * (Klog K + N^2))입니다. N=100, M=1000, K=1000일 때 약 1,100만 번의 연산으로 제한 시간 5초 내에 충분히 통과합니다.
2. 추론 과정
-
“M시간 동안”: 반복문(while/for)을 통한 시간 흐름 제어 필요.
-
“동시 이동”: 한 군집이 이동할 때 다른 군집의 ‘이전 위치’에 영향을 주면 안 됩니다. 즉, 새로운 상태를 기록할 별도의 공간(Map 또는 임시 리스트)이 필요함을 인지해야 합니다.
-
“가장 많은 미생물 수의 방향”: ‘정렬’ 혹은 ‘최댓값 비교’가 핵심임을 파악해야 합니다.
3. 설계 및 접근
-
미생물 클래스 정의: 위치, 수, 방향을 담고
Comparable을 구현하여 수량 내림차순 정렬. - 이동 처리:
- PQ에서 하나씩 꺼내 다음 좌표 계산.
- 약품 구역(경계) 도달 시: 수량 / 2, 방향 반전. 수량이 0이면 소멸.
- 병합 처리:
- map[r][c]가 비어있으면 현재 군집을 배치.
- 이미 누군가 있다면? 이미 들어있는 놈이 무조건 더 큽니다(PQ 덕분). 따라서 현재 군집의 수량만 더해주면 끝!
- 상태 복구: map에 있는 미생물들을 다시 PQ에 넣고 다음 턴 준비.
4. 예시 시뮬레이션
상황: (1,1)에 10마리(우), (1,3)에 20마리(좌)가 1초 뒤 (1,2)에서 만날 때
- Step 1 (PQ 정렬): [20마리(좌), 10마리(우)] 순서로 정렬됨.
- Step 2 (20마리 처리): (1,2)로 이동.
map[1][2]는 비었으므로map[1][2] = 20마리(좌). - Step 3 (10마리 처리): (1,2)로 이동.
map[1][2]에 이미 20마리 군집이 있음. - Step 4 (병합):
map[1][2]의 수량은 20+10 = 30이 됨. 방향은 그대로 좌측 유지.
5. 주의 사항
-
실수 포인트 1 (방향 전환): 상(1)↔하(2), 좌(3)↔우(4) 전환 시 비트 연산이나 조건문을 정확히 써야 합니다.
-
실수 포인트 2 (미생물 소멸):
cnt / 2를 했을 때 0이 되면 아예 맵에 표시하거나 PQ에 다시 넣으면 안 됩니다.
6. 코드 풀이
6.1 미생물 클래스 정의
static class Micro implements Comparable<Micro> {
int r, c, cnt, dir; // cnt: 현시간의 군집의 크기, total: 협쳐지는 군집의 크기
public Micro(int r, int c, int cnt, int dir) {
super();
this.r = r;
this.c = c;
this.cnt = cnt;
this.dir = dir;
}
@Override
public int compareTo(Micro o) {
// TODO Auto-generated method stub
return Integer.compare(o.cnt, this.cnt); // 군집의 크기가 큰 순 (상대 - 나)
}
}
- 위치, 수, 방향을 담고
Comparable을 구현하여 수량 내림차순 정렬
6.2 이동 처리
// 가장 자리 셀인 경우는 크기 1/2, 방향 반대로
if (nr == 0 || nr == N - 1 || nc == 0 || nc == N - 1) {
cur.cnt = cur.cnt / 2;
if (cur.cnt == 0)
continue; // 군집 소멸되었으면 아래 처리 skip하고 다음 군집으로
// 방향 반전
if (cur.dir % 2 == 1)
cur.dir++;
else
cur.dir--;
}
- PQ에서 하나씩 꺼내 다음 좌표 계산.
- 약품 구역(경계) 도달 시:
수량 / 2,방향 반전.- 수량이 0이면 소멸.
6.3 병합 처리
// 업데이트된 좌표로 이동하며 병합
if (map[nr][nc] == null) { // 이동하는 위치에 자신이 처음 도착한 경우
map[nr][nc] = cur;
} else { // 이동하는 위치에 먼저 도착한 군집이 있다면 자신보다 더 큰 군집이므로 흡수 당함
map[nr][nc].cnt += cur.cnt;
}
map[r][c]가 비어있으면 현재 군집을 배치.- 이미 누군가 있다면? 이미 들어있는 놈이 무조건 더 큽니다(PQ 덕분). 따라서 현재 군집의 수량만 더해주면 끝!
6.4 상태 복구
static int reset() {
int result = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c] == null)
continue;
result += map[r][c].cnt;
pq.offer(map[r][c]);
map[r][c] = null;
}
}
return result;
}
map에 있는 미생물들을 다시 PQ에 넣고 다음 턴 준비.
6.5 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Solution {
static class Micro implements Comparable<Micro> {
int r, c, cnt, dir; // cnt: 현시간의 군집의 크기, total: 협쳐지는 군집의 크기
public Micro(int r, int c, int cnt, int dir) {
super();
this.r = r;
this.c = c;
this.cnt = cnt;
this.dir = dir;
}
@Override
public int compareTo(Micro o) {
// TODO Auto-generated method stub
return Integer.compare(o.cnt, this.cnt); // 군집의 크기가 큰 순 (상대 - 나)
}
}
static int N, M, K;
static int dr[] = { 0, -1, 1, 0, 0 }; // 상: 1, 하: 2, 좌: 3, 우: 4
static int dc[] = { 0, 0, 0, -1, 1 }; // 상: 1, 하: 2, 좌: 3, 우: 4
static PriorityQueue<Micro> pq; // 미생물 군집 리스트
static Micro[][] map; // 미생물의 이동 기록 (병합 관리 위해)
public static void main(String[] args) throws NumberFormatException, IOException {
// TODO Auto-generated method stub
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(in.readLine());
for (int tc = 1; tc <= TC; tc++) {
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
pq = new PriorityQueue<>(); // 미생물 군집 리스트 초기화
map = new Micro[N][N]; // 미생물의 시간에 따른 이동을 기록
for (int i = 0; i < K; i++) {
st = new StringTokenizer(in.readLine());
int r = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int cnt = Integer.parseInt(st.nextToken());
int dir = Integer.parseInt(st.nextToken());
pq.offer(new Micro(r, c, cnt, dir));
} // 미생물 군집 리스트 입력 끝
System.out.println("#" + tc + " " + solve());
}
}
private static int solve() { // M시간 격리 후 살아있는 미생물 수의 총합 리턴
int time = M, nr, nc, remainCnt = 0;
// M시간 동안 처리
while (--time >= 0) {
while (!pq.isEmpty()) {
Micro cur = pq.poll();
// 군집 다음 좌표로 퐈표 갱신
nr = cur.r += dr[cur.dir];
nc = cur.c += dc[cur.dir];
// 가장 자리 셀인 경우는 크기 1/2, 방향 반대로
if (nr == 0 || nr == N - 1 || nc == 0 || nc == N - 1) {
cur.cnt = cur.cnt / 2;
if (cur.cnt == 0)
continue; // 군집 소멸되었으면 아래 처리 skip하고 다음 군집으로
// 방향 반전
if (cur.dir % 2 == 1)
cur.dir++;
else
cur.dir--;
}
// 업데이트된 좌표로 이동하며 병합
if (map[nr][nc] == null) { // 이동하는 위치에 자신이 처음 도착한 경우
map[nr][nc] = cur;
} else { // 이동하는 위치에 먼저 도착한 군집이 있다면 자신보다 더 큰 군집이므로 흡수 당함
map[nr][nc].cnt += cur.cnt;
}
} // end while pq
remainCnt = reset();
} // end while time
return remainCnt;
}
static int reset() {
int result = 0;
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
if (map[r][c] == null)
continue;
result += map[r][c].cnt;
pq.offer(map[r][c]);
map[r][c] = null;
}
}
return result;
}
}