SWEA 2382번 - 미생물 격리 [JAVA]
시간 제한: 50개 TC 5초 / 메모리 제한: 256MB
문제 요약
- 최초 각 미생물 군집의 위치와 군집 내 미생물의 수, 이동 방향이 주어진다. 약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.
- 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.
- 미생물 군집이 빨간색에 닿으면 군집 내 미생물의 절반이 죽고(소수점 버림), 이동방향이 반대로 바뀐다.
- 미생물 수가 0이 되면, 군집이 사라진다.
- 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다. 합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다. 합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.
M 시간 동안 이 미생물 군집들을 격리하였다. M시간 후 남아 있는 미생물 수의 총합을 구하여라.
제약 사항
- 구역의 모양은 정사각형으로 주어지며, 한 변의 셀의 개수 N은 5이상 100이하의 정수
- 미생물 군집의 개수 K는 5이상 1,000이하의 정수
- 격리 시간 M은 1이상 1,000이하의 정수
- 각 군집 내 미생물 수는 1 이상 10,000 이하의 정수
접근
누가봐도 시뮬레이션 문제. 하라는 대로 잘 하면 되지만 주의를 해야하는 부분은 미생물 군집이 합쳐질 때이다.
1. NAIVE
N * N에 해당하는 ArrayList 배열을 만들고, 좌표에 맞게 미생물 군집을 append 해준다. 군집이 2개 이상인 좌표에 대해 하나로 합쳐주는 과정을 거친다.
for (1 to M) {
ArrayList<군집 정보(미생물 수, 방향)> list[N][N];
for (미생물 군집 G : 미생물 군집 집합) {
미생물 군집 G 이동 수행
list[이동 후 G의 x좌표][이동 후 G의 y좌표].append({이동 후 G의 미생물 수, 방향});
}
for (i = 1 to N) {
for (j = 1 to N) {
if (list[i][j].size() == 0) continue;
int cnt = 0, max = 0, dir = 0;
for (k = 1 to list[i][j].size()) {
cnt += list[i][j].get(k)[0];
if (max < list[i][j].get(k)[0]) { // 군집이 2개 이상일 때, 가장 큰 군집의 방향을 따라가기 위함
max = list[i][j].get(k)[0];
dir = list[i][j].get(k)[1];
}
}
새로운 미생물 군집 집합에 미생물 군집 정보 push
}
}
현 미생물 군집 집합을 새롭게 만든 미생물 군집 집합으로 교체 (다음 스텝을 위한)
}시간 복잡도: \( O(M*(N^2 + K)) \)
SWEA 문제 특성상 모든 테케가 극한으로 들어오지 않기 때문에 통과할 것 같은데 이중 포문 사용으로 시간이 많이 걸리기도 하고 코드 길이가 길어져 구현도 귀찮을 것 같다.
2. 정렬
잘 생각해보면, 굳이 N * N 배열을 만들지 않고도 군집을 합칠 수 있다. ArrayList<{미생물 x좌표, y좌표, 미생물 수, 방향}>을 만들고, 미생물 x, y좌표, 미생물 수 순서대로 오름차순 정렬을 수행하면 된다.
압축 과정은 간단한 반복문을 통해 잘 구현할 수 있을 겁니다.. 따로 수도 코드를 넣진 않을게요..
시간 복잡도: \( O(M*KlgK) \)
3. Map - merge 메소드
해당 스텝의 미생물 군집을 움직이고, 리스트에 push하고, 정렬하고, 합치고, 다음 스텝의 군집 리스트에 푸시하고,,, 시간복잡도를 대폭 줄일 수 있지만..
역시나 귀찮다. 군집이 이동한 좌표에 군집 정보를 넣으면 해당 좌표에 있는 이전 값과 비교해 자동으로 합쳐지게 만들면(압축) 편할 것 같다는 생각이 들었다. 그래서 생각난게 Map 자료구조의 merge 메소드이다.
Map 의 `merge()` 메소드란?
`merge()` 메소드는 키가 존재하면 값을 갱신하고, 없으면 새 값을 추가하는 기능을 제공합니다.
public V merge( K key, V value, java.util.function.BiFunction<? super V, ? super V, ? extends V> remappingFunction )
- 키(key)가 없으면 → value를 그대로 삽입.
- 키(key)가 있으면 → 기존 값과 value를 remappingFunction을 이용해 병합 후 갱신.
간단한 예제
import java.util.HashMap; import java.util.Map; public class Main { public static void main(String[] args) { Map<String, String> map = new HashMap<>(); map.put("hello", "Hi"); // "hello" 키가 존재하므로 문자열을 이어붙임 map.merge("hello", " ssafy13!", (oldVal, newVal) -> oldVal + newVal); // "bye" 키가 없으므로 새 값 추가 map.merge("bye", "Goodbye!", (oldVal, newVal) -> oldVal + newVal); System.out.println(map); } } 실행결과 -> {hello=Hi ssafy13!, bye=Goodbye!}
그러면 같은 좌표가 들어왔을 때 merge를 잘 시켜줘야겠죠? 위의 정렬에서 같은 좌표에 있는 군집의 미생물 수의 max 값을 이용해서 방향을 정해줬던 것처럼, Map의 merge 메소드 내부에서도 이를 이용해서 군집의 최종 이동 방향을 정할 수 있게 해주면 된다. 그러면 Map<좌표정보, {현재 좌표의 총 미생물 수, 최종 이동 방향, 군집 중 최대 미생물 수}> 로 정의할 수 있다.
이제 코드 흐름을 생각해보면
- Map<좌표정보, {…}> step 변수에서 군집 정보를 하나씩 가져온다.
- 군집을 움직인다.
- 새로 만든 Map<좌표정보, {…}> nextStep 변수에 이동된 군집 정보를 merge한다.
- step 변수의 내용을 nextStep 내용으로 교체한다. (step = nextStep — copy by referece)
그런데 문제가 있다. Map의 key에 넣을 좌표정보를 int[]나 새로운 class를 만들어 정의하게 되면 문제(혹은 귀찮음)가 생긴다.
Map 자료구조의 Key 비교 방식
- HashMap → hashCode() & equals()
- TreeMap → compareTo() or Comparator
HashMap을 쓰려고 했더니 hashCode()는 메모리 주소 기반으로 생성된다.. 따라서 내용이 같더라도 다른 객체로 인식되어 올바른 value를 찾을 수 없다. 오버라이드 해줘야함..
TreeMap을 쓰려고 했더니 comparator 만들어야함..
둘 다 구현하기 귀찮다. 좋은 방법이 없을까? 다시 미생물 군집의 좌표를 봤다. X좌표와 Y좌표 모두 100 이하의 정수이다.
X와 Y를 붙여서 XY꼴의 integer로 만들면 Map<Integer, {…}>꼴로 만들어 쉽게 관리할 수 있다!
XY로 붙이는 것도 간단하다. X * 1000 + Y로 만들면 되고, 분리할 때도, X좌표는 XY / 1000 , Y좌표는 XY % 1000으로 쉽게 떼어낼 수 있다!
핵심 코드
// 상 하 좌 우
final static int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
public void solve(int testNumber) {
int n = in.nextInt(), t = in.nextInt(), m = in.nextInt();
// 좌표 -> 총 미생물 수, 방향, 합칠 때 최대 미생물 수
HashMap<Integer, int[]> step = new HashMap<>(), nextStep;
for (int i = 0; i < m; i++) { // 미생물 군집 정보 받고 step에 넣기
int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), d = in.nextInt();
step.put(1000 * a + b, new int[] {c, d - 1, 0});
}
while (t-- > 0) {
nextStep = new HashMap<>();
for (Entry<Integer, int[]> entry : step.entrySet()) {
int x = entry.getKey() / 1000, y = entry.getKey() % 1000;
int[] v = entry.getValue();
x += dx[v[1]]; y += dy[v[1]]; // 군집 이동
if (x == 0 || x == n - 1 || y == 0 || y == n - 1) { // 빨간색 닿으면
v[0] /= 2;
v[1] ^= 1; // 방향 바꿔줌 0->1, 1->0, 2->3, 3->2
}
v[2] = v[0];
nextStep.merge(1000 * x + y, v, (oldV, newV) -> {
return new int [] {
oldV[0] + newV[0], // 총 미생물 수
oldV[2] > newV[0] ? oldV[1] : newV[1], // 지금까지 추가된 군집 중 최대 미생물 수와 새로 들어올 군집의 미생물 수를 비교해서 방향 결정
Math.max(oldV[2], newV[0]) // 최대 미생물 수 갱신
};
});
}
step = nextStep;
}
out.println("#" + testNumber + " " + step.values().stream().mapToInt(v -> v[0]).sum());
}
시간 복잡도: HashMap사용 시 \( O(M*K) \) 이지만 상수가 커 생각보다 느림 / TreeMap 사용 시 \( O(M*KlgK) \)
전체 코드
import java.io.*;
import java.lang.*;
import java.util.*;
import java.util.Map.Entry;
public class Solution {
public static void main(String args[]) throws Exception {
InputReader in = new InputReader();
PrintWriter out = new PrintWriter(System.out);
int tests = in.nextInt();
for (int i = 1; i <= tests; i++) (new Task(in, out)).solve(i);
out.close();
}
static class Task {
static InputReader in;
static PrintWriter out;
Task(InputReader in, PrintWriter out) {
this.in = in;
this.out = out;
}
final static int INF = (int) 1e9;
final static int MOD = (int) 1e9 + 7;
// 상 하 좌 우
final static int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
public void solve(int testNumber) {
int n = in.nextInt(), t = in.nextInt(), m = in.nextInt();
// 좌표 -> 미생물 수, 방향, 합칠 때 최대 미생물 수
HashMap<Integer, int[]> step = new HashMap<>(), nextStep;
for (int i = 0; i < m; i++) {
int a = in.nextInt(), b = in.nextInt(), c = in.nextInt(), d = in.nextInt();
step.put(1000 * a + b, new int[] {c, d - 1, 0});
}
while (t-- > 0) {
nextStep = new HashMap<>();
for (Entry<Integer, int[]> entry : step.entrySet()) {
int x = entry.getKey() / 1000, y = entry.getKey() % 1000;
int[] v = entry.getValue();
x += dx[v[1]]; y += dy[v[1]];
if (x == 0 || x == n - 1 || y == 0 || y == n - 1) {
v[0] /= 2;
v[1] ^= 1;
}
v[2] = v[0];
nextStep.merge(1000 * x + y, v, (oldV, newV) -> {
return new int [] {
oldV[0] + newV[0],
oldV[2] > newV[0] ? oldV[1] : newV[1],
Math.max(oldV[2], newV[0])
};
});
}
step = nextStep;
}
out.println("#" + testNumber + " " + step.values().stream().mapToInt(v -> v[0]).sum());
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader() {
reader = new BufferedReader(new InputStreamReader(System.in));
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() { return Integer.parseInt(next()); }
public long nextLong() { return Long.parseLong(next()); }
public double nextDouble() { return Double.parseDouble(next()); }
public String nextLine() {
String str = "";
try {
str = reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
return str;
}
}
}
