[SWEA] 5653. 줄기세포배양

• 메모리 : 94,044 KB
• 실행시간 : 345 ms
• 코드길이 : 2,955 B
• 소요시간 : 1H
• 문제에서 말한 것을 그대로 BFS로 구현하는 것 자체도 꽤 까다로웠다. 비활성 상태의 세포도 고려해야하고 세포마다 퍼지는 시간이 달라서 이 모든 것을 생각하고 처리해주어야 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution_5653_줄기세포배양 {

	static int size = 400, N, M, K, res;
	static int[][] map;
	static List<ArrayList<Data>> cells;
	static int[][] delta = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 상 우 하 좌

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder answer = new StringBuilder();

		int TC = Integer.parseInt(in.readLine());
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(in.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[size][size];
			cells = new ArrayList<>();
			res = 0;

			for (int i = 0; i < 10; i++) {
				cells.add(new ArrayList<Data>());
			}

			for (int i = size / 2; i < N + size / 2; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = size / 2; j < M + size / 2; j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
					if (map[i][j] > 0)
						cells.get(map[i][j] - 1).add(new Data(i, j, map[i][j], map[i][j], K, false));
				}
			}

			bfs();

			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					if (map[i][j] > 0)
						res++;
				}
			}

			answer.append('#').append(t).append(' ').append(res).append('\n');
		} // end test-case

		System.out.println(answer);
	} // end main

	private static void bfs() {
		Queue<Data> queue = new LinkedList<Data>();

		for (int i = 9; i >= 0; i--) {
			if (cells.get(i).size() > 0) {
				for (Data data : cells.get(i)) {
					queue.offer(data);
				}
			}
		} // end for cells

		Data cur;
		while (!queue.isEmpty()) {
			cur = queue.poll();

			if (cur.life == 0 && cur.isActive) {
				map[cur.i][cur.j] = -1;
				continue;
			}

			if (cur.k == 0)
				continue;

			if (cur.life > 0) {
				queue.offer(new Data(cur.i, cur.j, cur.x, cur.life - 1, cur.k - 1, cur.isActive));
				continue;
			}

			queue.offer(new Data(cur.i, cur.j, cur.x, cur.x, cur.k, true));

			for (int d = 0; d < delta.length; d++) {
				int curX = cur.i + delta[d][0];
				int curY = cur.j + delta[d][1];

				if (map[curX][curY] == 0) {
					map[curX][curY] = cur.x;
					queue.offer(new Data(curX, curY, cur.x, cur.x, cur.k - 1, false));
				}
			}
		} // end while
	} // end bfs

	static class Data {
		int i;
		int j;
		int x; // 줄기세포 생명력

		int life; // 줄기세포 생명력
		int k; // 배양시간 K
		boolean isActive; // 활성상태 ture, 비활성상태 false

		public Data(int i, int j, int x, int life, int k, boolean isActive) {
			this.i = i;
			this.j = j;
			this.x = x;
			this.life = life;
			this.k = k;
			this.isActive = isActive;
		}
	}
}

Priority Queue

• 메모리 : 47,372 KB
• 실행시간 : 207 ms
• 코드길이 : 2,350 B
• 소요시간 : 40M

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Solution_5653_줄기세포배양_PQ {

	static int size = 400, N, M, K, res;
	static boolean[][] visited;
	static PriorityQueue<Data> cells;
	static int[][] delta = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; // 상 우 하 좌

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder answer = new StringBuilder();

		int TC = Integer.parseInt(in.readLine());
		for (int t = 1; t <= TC; t++) {
			st = new StringTokenizer(in.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			visited = new boolean[size][size];
			cells = new PriorityQueue<Data>();
			res = 0;

			for (int i = size / 2; i < N + size / 2; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				for (int j = size / 2; j < M + size / 2; j++) {
					int x = Integer.parseInt(st.nextToken());
					if (x > 0) {
						visited[i][j] = true;
						cells.offer(new Data(i, j, x, x + 1));
						if (x * 2 > K) res++; // K시간보다 크면 비활성상태일 것이기 때문에 미리 카운트
					}
				}
			}

			bfs();

			answer.append('#').append(t).append(' ').append(res).append('\n');
		} // end test-case

		System.out.println(answer);
	} // end main

	private static void bfs() {
		int time = 0;
		Data cur;

		while (time <= K) {
			cur = cells.poll();
			time = cur.time;

			if (time > K) break;

			for (int d = 0; d < delta.length; d++) {
				int curX = cur.i + delta[d][0];
				int curY = cur.j + delta[d][1];

				if (!visited[curX][curY]) {
					visited[curX][curY] = true;
					cells.offer(new Data(curX, curY, cur.x, time + cur.x + 1));

					if (time + cur.x * 2 > K) res++;
				}
			}
		}
	} // end bfs

	static class Data implements Comparable<Data> {
		int i;
		int j;
		int x; // 줄기세포 생명력

		int time; // 활성화 시간

		public Data(int i, int j, int x, int time) {
			this.i = i;
			this.j = j;
			this.x = x;

			this.time = time;
		}

		@Override
		public int compareTo(Data o) {
			if (time != o.time) return Integer.compare(time, o.time);
			return -Integer.compare(x, o.x);
		}
	}
}