문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV597vbqAH0DFAVl

---

입력

첫 줄에는 총 테스트 케이스의 개수 T가 주어진다.
그 다음 줄부터 T개의 테스트 케이스가 차례대로 주어진다.
각 테스트 케이스의 첫째 줄에는 구역의 한 변에 있는 셀의 개수 N, 격리 시간 M, 미생물 군집의 개수 K가 순서대로 주어지며, 다음 K줄에 걸쳐서 미생물 군집 K개의 정보가 주어진다.

---

출력

각 테스트 케이스마다 M시간 후 남아 있는 미생물 수의 총 합

---

풀이

제한조건

• (5 ≤ N ≤ 100)
• (5 ≤ K ≤ 1,000)
• (1 ≤ M ≤ 1,000)

접근방법

시뮬레이션

문제를 차근차근 읽고 정리해보자.

1. 1시간 마다 미생물은 이동한다.
2. 미생물 군집이 약품이 칠해진 부분에 도착하면 수가 절반으로 줄어든다.
3. 미생물 군집끼리 같은 칸에 도달하면, 수는 합치고 방향은 가장 많은 미생물의 방향을 따른다.

문제는 길어보이지만 제법 단순한 문제다.
단순 시뮬레이션을 통해 해결이 가능하므로, 몇 가지만 짚어보자.

1. 인접 방향
군집의 이동방향은 상하좌우 4방향 중 한 방향을 가진다. (상: 1, 하: 2, 좌: 3, 우: 4)
시계방향으로 연결된것이 아니다..!
각 방향에 따라 반대방향이 어디인지 잘 찾아주어야 한다.

2. 관점
문제를 해결하는 방향 중

• 미생물을 기준으로 생각
• 각 좌표를 기준으로 생각
  2가지로 문제를 해결할 수 있다.

아래 코드에서는 각 좌표를 기준으로 접근했다.
각 지점을 기준으로 인접한 방향에서 현재 지점으로 이동하는 미생물이 있는지 확인하고 이후 동작을 수행하는 방식으로 구현한다면, 조금 더 단순하게 접근할 수 있다.

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
	static class Info {
		int num;
		int dir;

		Info(int num, int dir) {
			this.num = num;
			this.dir = dir;
		}
	}

	static int N, M, K, numRemain;
	static int[][] arr, newArr;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static StringBuilder sb = new StringBuilder();
	static Info[] infos;

	public static void main(String[] args) throws Exception {
		// input
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int T = stoi(in.readLine());

		for (int tc = 0; tc < T; ++tc) {
			String[] inputs = in.readLine().split(" ");
			N = stoi(inputs[0]);
			M = stoi(inputs[1]);
			K = stoi(inputs[2]);
			arr = new int[N][N];
			infos = new Info[K];
			for (int i = 0; i < K; ++i) {
				inputs = in.readLine().split(" ");
				int x = stoi(inputs[0]);
				int y = stoi(inputs[1]);
				int num = stoi(inputs[2]);
				int dir = stoi(inputs[3]) - 1;

				infos[i] = new Info(num, dir);
				arr[x][y] = i + 1;
			}

			int result = getTotalSum();
			sb.append("#").append(tc + 1).append(" ").append(result).append("\n");
		}
		System.out.println(sb);
	}

	private static int getTotalSum() {
		numRemain = K;

		for (int tc = 0; tc < M; ++tc) {
			if (numRemain == 0)
				break;
			newArr = new int[N][N];
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < N; ++j) {
					newArr[i][j] = simulation(i, j);
				}
			}
			for (int i = 0; i < N; ++i) {
				if (newArr[i][0] != 0) {
					int idx = newArr[i][0] - 1;
					infos[idx].num = infos[idx].num / 2;
					infos[idx].dir = getReverseDir(infos[idx].dir);
					if (infos[idx].num == 0)
						newArr[i][0] = 0;
				}
				if (newArr[i][N - 1] != 0) {
					int idx = newArr[i][N - 1] - 1;
					infos[idx].num = infos[idx].num / 2;
					infos[idx].dir = getReverseDir(infos[idx].dir);
					if (infos[idx].num == 0)
						newArr[i][N - 1] = 0;
				}
				if (newArr[0][i] != 0) {
					int idx = newArr[0][i] - 1;
					infos[idx].num = infos[idx].num / 2;
					infos[idx].dir = getReverseDir(infos[idx].dir);
					if (infos[idx].num == 0)
						newArr[0][i] = 0;
				}
				if (newArr[N - 1][i] != 0) {
					int idx = newArr[N - 1][i] - 1;
					infos[idx].num = infos[idx].num / 2;
					infos[idx].dir = getReverseDir(infos[idx].dir);
					if (infos[idx].num == 0)
						newArr[N - 1][i] = 0;
				}
			}
			arr = newArr;
		}

		int sum = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				int idx = arr[i][j];
				if (idx == 0)
					continue;
				sum += infos[idx - 1].num;
			}
		}
		return sum;
	}

	private static int getReverseDir(int dir) {
		if (dir == 0)
			return 1;
		if (dir == 1)
			return 0;
		if (dir == 2)
			return 3;
		if (dir == 3)
			return 2;
		return -1;
	}

	private static int simulation(int x, int y) {
		int maxIdx = -1;
		int maxNum = -1;
		int sum = 0;
		int count = 0;
		for (int d = 0; d < 4; ++d) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			if (!isInRange(nx, ny))
				continue;
			int next = arr[nx][ny] - 1;

			// 옆이 빈자리였다 생략.
			if (next == -1)
				continue;

			// 옆 자리의 미생물이 현재 위치로 이동하는 것이 아니라면 생략
			int newDir = getReverseDir(infos[next].dir);
			if (newDir != d)
				continue;

			if (maxNum < infos[next].num) {
				maxNum = infos[next].num;
				maxIdx = next;
			}
			sum += infos[next].num;
			count++;
		}
		if (maxIdx == -1)
			return 0;
		infos[maxIdx].num = sum;
		numRemain -= (count - 1);

		return maxIdx + 1;
	}

	public static boolean isInRange(int x, int y) {
		if (0 <= x && x < N && 0 <= y && y < N)
			return true;
		return false;
	}

	public static int stoi(String s) {
		return Integer.parseInt(s);
	}
}