2382 미생물 격리

풀이 전략

1. BFS를 사용하며 시간의 흐름(M)를 구분함. (굳이 Q를 사용할 이유는 없다. 그저 내가 편하기 때문에 사용함.)

2. 각 군의 위치를 PriorityQueue에 넣어 매 시간의 흐름마다 위치를 계산함. 이때 계산된 값을 버퍼에 저장하여 다른 각군의 움직임에 따른 개수와 방향을 결정한다. (비효율적이긴 하지만 디버깅할 때는 이점이 있었다.)

 

3. PriorityQueue를 사용 or 정렬을 사용하지 않는다면, 다수의 군이 합쳐지는 경우, 방향이 제대로 결정되지 않아 오답이 나올 수 있다.

 

int Array에 대한 정렬은 아래와 같이 구현 가능하다. (size 및 lambda 식을 인자로 전달하면 된다)

PriorityQueue<int[]> Q = new PriorityQueue<>(4, (a, b) -> {
	return b[2] - a[2];
});

 

 

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileOutputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;

class Solution {

	static int N, M, K;
	static int[][][] map;
	static ArrayList<int[]> list;
	private static boolean DBG = false;
	static int[] dx = { 0, -1, 1, 0, 0 };
	static int[] dy = { 0, 0, 0, -1, 1 };
	static int num;

	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		if (DBG) {
			File file = new File("C:\\Users\\Lee\\eclipse-workspace\\TestApplication\\output.txt");
			PrintStream ps = new PrintStream(new FileOutputStream(file));
			System.setOut(ps);
		}

		int T;
		T = Integer.parseInt(br.readLine());

		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		long startTime = System.currentTimeMillis();
		for (int test_case = 1; test_case <= T; test_case++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			// K개의 군집, 좌표 및 미생물의 수, 방향
			list = new ArrayList<int[]>();
			if (DBG)
				System.out.printf("N : %d M : %d K : %d\n", N, M, K);
			for (int i = 0; i < K; i++) {

				st = new StringTokenizer(br.readLine());
				int r = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				int n = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken());

				list.add(new int[] { r, c, n, d });

			}
			num = 0;
			bfs();
			System.out.println("#" + test_case + " " + num);
		}
		if (DBG) {
			long duration = System.currentTimeMillis() - startTime;
			System.out.println("duration : " + duration + "ms");
		}
	}

	static void bfs() {
		PriorityQueue<int[]> Q = new PriorityQueue<>(4, (a, b) -> {
			return b[2] - a[2];
		});

		for (int[] ar : list)
			Q.offer(ar);

		int level = 0;

		while (!Q.isEmpty()) {
			int size = Q.size();
			// 1회 돌 때마다 map을 초기화
			map = new int[N][N][2];
			if (level == M) {
				for (int[] ar : Q) {
					num += ar[2];
				}
				if (DBG)
					System.out.printf("level : %d  M : %d num : %d\n", level, M, num);
				return;
			}

			for (int q = 0; q < size; q++) {
				int[] now = Q.poll();
				int r = now[0], c = now[1], n = now[2], d = now[3];
				int nr = r + dx[d];
				int nc = c + dy[d];
				if (nr == 0 || nr == N - 1 || nc == 0 || nc == N - 1) {
					// 방향 결정
					if (map[nr][nc][0] < n / 2) {
						map[nr][nc][1] = (d % 2 == 0) ? d - 1 : d + 1;
					}
					// 닿은 경우 절반으로 줄임
					map[nr][nc][0] += n / 2;
				} else {
					map[nr][nc][1] = map[nr][nc][0] < n ? d : map[nr][nc][1];
					map[nr][nc][0] += n;
				}

			}

			if (DBG) {
				System.out.println("level : " + level);
				for (int i = 0; i < N; i++) {
					for (int j = 0; j < N; j++) {
						System.out.printf("(%3d %3d) ", map[i][j][0], map[i][j][1]);
					}
					System.out.println();
				}
			}
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (map[i][j][0] != 0) {
						// if (DBG)
						// System.out.printf("offer %d %d %d %d\n", i, j, map[i][j][0], map[i][j][1]);
						Q.offer(new int[] { i, j, map[i][j][0], map[i][j][1] });
					}
				}
			}

			++level;

		}

	}

}

 

다른 풀이를 보면, 굳이 Queue를 사용할 필요는 없으며 ArrayList 및 for 문 만으로도 구현 가능하다.

 

아래 코드조각을 참조하면 각군에 대해 개별로 처리를 해준 뒤, sort하여 앞뒤 요소를 비교하여 좌표가 같으면 

합쳐준 뒤, 나머지를 삭제한다.

 

				//문자열의 pos 처럼 행렬의 값을 하나로 표시
                virus.num = (virus.i * N) + virus.j;
				
                ...
                
				Collections.sort(list);

                // 이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다.
                for (int idx = 0; idx < list.size() - 1; idx++) {
                    Virus now = list.get(idx);
                    Virus next = list.get(idx + 1);
					//같은 위치에 있을 경우, 하나로 합친뒤 나머지를 제거
                    if (now.num == next.num) {
                        now.cnt += next.cnt;
                        list.remove(idx + 1);
                        idx--;
                    }
                }