문제
문제 설명
정사각형 구역 안에 K개의 미생물 군집이 있다.
이 구역은 가로 N개, 세로 N개, 총 N * N 개의 동일한 크기의 정사각형 셀들로 이루어져 있다.
미생물들이 구역을 벗어나는걸 방지하기 위해, 가장 바깥쪽 가장자리 부분에 위치한 셀들에는 특수한 약품이 칠해져 있다.
[Fig. 1]은 9개의 군집이 한 변이 7개의 셀로 이루어진 구역에 배치되어 있는 예이다.
가장자리의 빨간 셀은 약품이 칠해져 있는 셀이다.
① 최초 각 미생물 군집의 위치와 군집 내 미생물의 수, 이동 방향이 주어진다. 약품이 칠해진 부분에는 미생물이 배치되어 있지 않다. 이동방향은 상, 하, 좌, 우 네 방향 중 하나이다.
② 각 군집들은 1시간마다 이동방향에 있는 다음 셀로 이동한다.
③ 미생물 군집이 이동 후 약품이 칠해진 셀에 도착하면 군집 내 미생물의 절반이 죽고, 이동방향이 반대로 바뀐다.
미생물 수가 홀수인 경우 반으로 나누어 떨어지지 않으므로, 다음과 같이 정의한다.
살아남은 미생물 수 = 원래 미생물 수를 2로 나눈 후 소수점 이하를 버림 한 값
따라서 군집에 미생물이 한 마리 있는 경우 살아남은 미생물 수가 0이 되기 때문에, 군집이 사라지게 된다,
④ 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
합쳐 진 군집의 미생물 수는 군집들의 미생물 수의 합이며, 이동 방향은 군집들 중 미생물 수가 가장 많은 군집의 이동방향이 된다.
합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 된다.
M 시간 동안 이 미생물 군집들을 격리하였다. M시간 후 남아 있는 미생물 수의 총합을 구하여라.
시간에 지남에 따라 군집이 변하는 예를 보자.
[Fig. 2]은 최초 군집의 배치를 그림으로 표현한 것이다. 이는 예제 입력 1번과 동일하다. (N = 7, K = 9)
1시간 후 [Fig. 3]과 같이 군집들이 이동한다.
A 군집은 약품이 칠해진 구역(가장 자리의 빨간 셀)로 이동하게 되어, 미생물 중3마리만 남고 나머지는 죽는다. 이동 방향은 상에서 하로 바뀐다.
D, E, F 군집은 모두 세로 위치 3, 가로 위치 3에 위치한 셀로 모이게 되며, 합쳐진 군집의 미생물 수는 8 + 14 + 3 = 25가 된다.
E 군집의 미생물 수가 가장 많기 때문에, 합쳐 진 군집의 이동 방향은 E 군집의 이동 방향인 상이 된다.
G, H 군집도 세로 위치 2, 가로 위치 5에 위치한 셀로 모이게 되며, 미생물 수는 108이 되고 이동 방향은 상이 된다.
시작으로부터 2시간이 지났을 때, [Fig. 4]와 같이 군집들이 이동한다.
A, B 그룹은 이동 중 섞이지 않고 각 그룹의 이동 방향으로 움직이는데, B 그룹은 약품이 칠해진 셀로 이동하므로 미생물 수가 7에서 3으로 반감하고, 이동 방향이 상에서 하로 바뀐다.
2시간이 지난 후, 남아 있는 미생물 수는 총 3 + 3 + 5 + 25 + 108 + 1 = 145이다.
제한 사항
1. 시간제한 : 최대 50개 테스트 케이스를 모두 통과하는데, C/C++/Java 모두 5초
2. 구역의 모양은 정사각형으로 주어지며, 한 변의 셀의 개수 N은 5이상 100이하의 정수이다. (5 ≤ N ≤ 100)
3. 최초 배치되어 있는 미생물 군집의 개수 K는 5이상 1,000이하의 정수이다. (5 ≤ K ≤ 1,000)
4. 격리 시간 M은 1이상 1,000이하의 정수이다. (1 ≤ M ≤ 1,000)
5. 최초 약품이 칠해진 가장자리 부분 셀에는 미생물 군집이 배치되어 있지 않다.
6. 최초에 둘 이상의 군집이 동일한 셀에 배치되는 경우는 없다.
7. 각 군집 내 미생물 수는 1 이상 10,000 이하의 정수이다.
8. 군집의 이동방향은 상하좌우 4방향 중 한 방향을 가진다. (상: 1, 하: 2, 좌: 3, 우: 4)
9. 주어진 입력으로 진행하였을 때, 동일한 셀에 같은 미생물 수를 갖는 두 군집이 모이는 경우는 발생하지 않는다.
10. 각 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 주어진다. 각 위치는 0번부터 시작한다.
입출력 예
[입력]
첫 줄에는 총 테스트 케이스의 개수 T가 주어진다.
그 다음 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫째 줄에는 구역의 한 변에 있는 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K가 순서대로 주어지며, 다음 K줄에 걸쳐서 미생물 군집 K개의 정보가 주어진다.
미생물 군집의 정보는 세로 위치, 가로 위치, 미생물 수, 이동 방향 순으로 4개의 정수가 주어진다.
[출력]
테스트 케이스의 개수 만큼 T개의 줄에 각 테스트 케이스에 대한 답을 출력한다.
각 줄은 “#x”로 시작하고, 공백을 하나 둔 후 정답을 출력한다. (x는 테스트 케이스의 번호이며, 1번부터 시작한다.)
출력해야 할 정답은 M시간 후 남아 있는 미생물 수의 총 합이다.
제출 코드
import java.io.*;
import java.security.KeyStore;
import java.util.*;
/*
@author ranuinclulus
@since 2024.08.27
@link
@timecomplex
@performance 22764KB, 182MS
@category
@note DFS
*/
public class Solution {
class Micro implements Comparable<Micro> {
int row;
int col;
int num;
int direction;
int index;
public Micro(int row, int col, int num, int direction, int index) {
this.row = row;
this.col = col;
this.num = num;
this.direction = direction;
this.index = index;
}
@Override
public int compareTo(Micro o) {
return -Integer.compare(num, o.num);
}
}
class Position {
int row;
int col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Position position = (Position) o;
return row == position.row && col == position.col;
}
@Override
public int hashCode() {
return 10 * row + col;
}
}
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int testNum;
static int n;
static int m;
static int k;
static Micro[] micros;
static int[][] deltas = new int[][] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public void solution() throws IOException {
testNum = Integer.parseInt(br.readLine());
for (int test = 1; test <= testNum; test++) {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
k = Integer.parseInt(st.nextToken());
micros = new Micro[k];
for (int i = 0; i < k; i++) {
st = new StringTokenizer(br.readLine());
micros[i] = new Micro(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()) - 1,
i);
}
while (m --> 0) {
HashMap<Position, Integer> map = new HashMap<>();
for (Micro micro : micros) {
if (micro.num == 0) continue; // 이미 죽은 애면 패스
int nextRow = micro.row + deltas[micro.direction][0];
int nextCol = micro.col + deltas[micro.direction][1];
// 벽에 부딪힌 경우
if (nextRow == 0 || nextRow == n - 1 || nextCol == 0 || nextCol == n - 1) {
micro.num /= 2;
// 죽지 않았다면
if (micro.num != 0) {
// 방향 반대
if (micro.direction == 0 || micro.direction == 2) {
micro.direction++;
} else micro.direction--;
}
}
// 벽에 부딪히지 않은 경우
micro.row = nextRow;
micro.col = nextCol;
Position position = new Position(micro.row, micro.col);
map.put(position, map.getOrDefault(position, 0) + 1);
}
for(Map.Entry<Position, Integer> entry : map.entrySet()) {
if (entry.getValue() == 1) continue;
List<Micro> candidate = new LinkedList<>();
for(Micro micro : micros) {
if (micro.row == entry.getKey().row && micro.col == entry.getKey().col) {
candidate.add(micro);
}
}
Collections.sort(candidate);
int plus = 0;
for (int i = 1; i < candidate.size(); i++) {
plus += candidate.get(i).num;
micros[candidate.get(i).index].num = 0;
}
micros[candidate.get(0).index].num += plus;
}
}
int total = 0;
for(Micro micro : micros) {
total += micro.num;
}
sb.append("#").append(test).append(" ").append(total).append("\n");
}
bw.write(sb.toString());
bw.flush();
}
public static void main(String[] args) throws IOException {
new Solution().solution();
}
}
코드 설명
Micro 객체
- 미생물의 row, col 위치
- 미생물의 크기
- 미생물이 보고 있는 방향
- 미생물이 담긴 배열의 인덱스를 저장
- 미생물은 크기가 클수록 우선 순위를 가지도록 Comparable 재정의
입력부
- n: 지도의 사이즈
- m: 몇 초를 보낼 건지
- k: 미생물의 개수
미생물의 이동
- 이미 죽어서 크기가 0인 미생물이면 패스
- nextRow, nextCol로 미생물이 바라보는 방향으로 한 칸 전진했을 경우의 좌표를 얻음
- 벽에 부딪힌 경우
- 사이즈 반띵
- 반띵했는데 죽지 않았다면 방향을 반대로 바꿔 줌
- 반띵 후 죽었다면 어차피 다음 반복에서 continue로 걸러질 것이기 때문에 따로 죽었다고 표시 안 해 줌
- 벽에 부딪히지 않은 경우 그냥 전진
만약 같은 칸에서 만난다면?
-
이 경우 D, E, F 미생물이 모두 (3, 3) 에서 만나게 됨
-
가장 큰 사이즈인 14의 방향으로 설정되고 크기를 모두 합침 → (14 + 8 + 3) 사이즈를 가지고 위를 바라보는 미생물로 합체
-
이를 확인하기 위해 미생물이 이동할 예정인 좌표들을 hash의 키로 넣고, 해당 좌표들이 얼마나 나왔는지를 value로 확인함
-
예를 들어 위의 그림과 같은 경우에는 hash에 <{3, 3}, 3> 으로 담기게 되는 것
-
해시에서 키 값인 좌표 두 개를 같게 인지하게 하기 위해 비교 연산을 정의할 수 있도록 Position이라는 객체 생성
- equals와 hashCode 재정의해서 row와 col이 같다면 같은 객체로 인지하도록 함
충돌하는 칸 값 업데이트
- 만약 한 번만 나온 좌표라면 겹치지 않는 거니까 패스
- 두 번 이상 나온 좌표라면 미생물을 순회하면서 그 좌표에 있는 미생물들을 candidate라는 list에 넣음
- 앞선 예시로 따지자면 3, 8, 14 값을 가진 미생물들이 리스트에 들어가는 것
- 미생물을 정렬함 → 크기순으로 정렬됨
- 정렬된 리스트 중에서 두 번째 값부터 끝까지는 크기를 0으로 만들고, 두 번째 값부터 끝까지의 미생물들의 값을 합한 수를 첫 번째에 더해 줌
- 이렇게 하면 한 턴 완성
