문제

https://swexpertacademy.com/main/code/problem/problemDetail.do

코드 (Java)

import java.util.*;
import java.io.*;

class Solution
{
	
	private static final int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	
	public static class Node {
		int row;
		int col;
		int genTime;
		int lifeStat;
		Node nextNode = null;
		Node prevNode = null;
		boolean isHead = false;
		
		Node(int row, int col, int gen_time, int life_stat) {
			this.row = row;
			this.col = col;
			this.genTime = gen_time;
			this.lifeStat = life_stat;
		}
		
		void putNext(Node nextNode) {
			nextNode.prevNode = this; 
			nextNode.nextNode = this.nextNode;
			if (this.nextNode != null) {
				this.nextNode.prevNode = nextNode;	
			}
			this.nextNode = nextNode;
		}
		
		void release() {
			if (this.prevNode != null)
				this.prevNode.nextNode = this.nextNode;
			if (this.nextNode != null)
				this.nextNode.prevNode = this.prevNode;
			
			this.nextNode = null;
			this.prevNode = null;
		}
		
		boolean isPending(int t) {
			return t < this.genTime + this.lifeStat;
		}
		
		boolean isActive (int t) {
			return t >= this.genTime + this.lifeStat 
					&& t < this.genTime + 2 * this.lifeStat;
		}
		
		boolean isDead (int t) {
			return t >= this.genTime + 2 * this.lifeStat;
		}
	}
	
	public static void main(String args[]) throws Exception
	{
//		System.setIn(new FileInputStream("res/input.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T;
		T = Integer.parseInt(br.readLine().trim());

		for(int test_case = 1; test_case <= T; test_case++)
		{
			StringTokenizer st = new StringTokenizer(br.readLine().trim());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int actCnt = 0;
			int pendCnt = 0;
			int time = 0;
			Node[][] relatedNode = new Node[351][351];
			Node pendHead = null;
			Node actHead = null;
			
			for (int row = 150; row < N+150; ++row) {
				st = new StringTokenizer(br.readLine());
				for (int col = 150; col < M+150; ++col) {
					int t = Integer.parseInt(st.nextToken());
					if (t != 0) {
						Node tNode = new Node(row, col, 0, t);
						if (pendHead == null) {
							pendHead = tNode;
							pendHead.isHead = true;
						}
						else pendHead.putNext(tNode);
						relatedNode[row][col] = tNode;
						++pendCnt;
					}
				}
			}
			
			if (pendCnt == 0) {
				//no microbe exist. Edge case.
				bw.write("#" + test_case + " " + pendCnt + "\n");
				continue;
			}
			
			while (time < K) {
				++time;
//				System.out.printf("before : test case %d, time %d, cnt %d\n", test_case, time, pendCnt + actCnt);
				// iterate active microbes
				Node nextAct = actHead;
				while (nextAct != null) {
//					System.out.printf("r %d c %d gen %d life %d node hit\n", nextAct.row, nextAct.col, nextAct.genTime, nextAct.lifeStat);
					int r = nextAct.row;
					int c = nextAct.col;
					for (int idx = 0; idx < 4; ++idx) {
						int newR = r + dir[idx][0];
						int newC = c + dir[idx][1];
						if (relatedNode[newR][newC] == null) {
							//we're the first to achieve that empty cell!
							Node newNode = new Node(newR, newC, time, nextAct.lifeStat);
							relatedNode[newR][newC] = newNode;
							if (pendHead == null) {
								pendHead = newNode;
								newNode.isHead = true;
							}
							else {
								pendHead.putNext(newNode);
							}
							++pendCnt;
						}
						else if (relatedNode[newR][newC].genTime == time && relatedNode[newR][newC].lifeStat < nextAct.lifeStat) {
							relatedNode[newR][newC].lifeStat = nextAct.lifeStat;
						}
					}
					
					Node tmpNext = nextAct.nextNode;
					
					if (nextAct.isDead(time)) {
						if (nextAct.isHead) {
							actHead = tmpNext;
							if (actHead != null) actHead.isHead = true;
							nextAct.isHead = false;
						}
//						if (actHead == null) System.out.println("is null");
//						else System.out.printf("actHead is now r %d c %d node\n", actHead.row, actHead.col);
						nextAct.release();
						--actCnt;
					}
					
					nextAct = tmpNext;
				}
				
				Node nextPend = pendHead;
				while (nextPend != null) {
					Node tmpNext = nextPend.nextNode;
					if (nextPend.isActive(time)) {
						if (nextPend.isHead) {
							pendHead = tmpNext;
							if (pendHead != null) pendHead.isHead = true;
							nextPend.isHead = false;
						}
						nextPend.release();
						--pendCnt;
						if (actHead == null) {
							actHead = nextPend;
							actHead.isHead = true;
						}
						else actHead.putNext(nextPend);
						++actCnt;
					}
					nextPend = tmpNext;
				}
				
//				System.out.printf("after : test case %d, time %d, cnt %d\n", test_case, time, pendCnt + actCnt);
			}
			
			bw.write("#" + test_case + " " + (pendCnt + actCnt) + "\n");
		}
		
		bw.flush();
		bw.close();
	}
}

풀이

• 시뮬레이션 + 구현 + BFS

• 문제에서 요구하는 사항이 어려워보이지는 않는데 요구 시간 안에 해결하기 위한 자료 구조 형성에 대해 고민하는데 시간을 좀 잡아 먹었다.

  • 배양공간의 크기 제한이 딱히 없기 때문에 가장 많이 퍼질 수 있는 공간의 크기를 계산해야 한다. 단순하게 생각할 때 700 x 700으로 생각이 가능해서 그렇게 풀었는데, 실제로는 대략 351 x 351으로 해도 된다. 활성화 후에 번식이 가능해서 번식을 하는데 기본 2초가 걸리고 최대 시간 제한이 300이기 때문에 좌우로 150씩생각 + 기본 최대 크기 50을 고려하면 저정도가 알맞다.

  • 이처럼 2차원 배열의 크기가 매우 크기 때문에 일일이 탐색하는 것이 그렇게 효율적이진 않다. 그래서 linked list를 통해 active/pending인 node들을 따로 모아서 그걸 iterate하기로 했다. 이 때 linked list를 직접 구현했는데, Java의 linked list가 iterate 도중 편집을 허용하지 않아서 그냥 따로 만들었다.

  • 나중에 든 생각인데 linked list 대신 Java의 priority queue를 활용해도 되지 않았을까 싶다. 그러면 좀 더 빨리 풀었을지도.