[SWEA] 5653.줄기세포배양 / BFS, 시뮬레이션

@BFS, 시뮬레이션

약간 난이도 있는 시뮬레이션.

어렵게 생겨서 엄청 쫄았는데 생긴 것 보다는 어렵지 않다. (쉽다는건 아님..)

구현은 1시간 10분정도 걸렸는데 44/50개로 계속 fail 떠서.. 이거 잡는데 한시간 걸렸다ㅠ

 

엄청 어려운 원리는 아닌데 문제를 꼼꼼히 안읽어서 삽질 많이 했다.

 

 

문제 링크

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

SW Expert Academy

 

구현 포인트

1. 세포가 번식해서 퍼져나가기기 때문에 BFS로 구현했다.

2. 큐에는 비활성, 활성 상태만 담고 세포가 죽으면 더 이상 큐에 넣지 않았다. 죽은 세포에 대한 처리를 별도로 하지 않았다.

3. 세포 번식의 경우 충돌은 큐에서 뺀 시점에 맵에 표시된 생명력과 지금 나의 생명력이 같으면 살리는 방식으로 풀었다.

해시맵을 쓸까도 고민해 봤지만, 일단 잘 안써봐서 자신이 없었고, 예전에 상어 풀었을때(백준 16236.아기상어)의 팁이 생각나서 이걸로 풀었다.

 

* Node 클래스 구성

 - 세포는 비활성(X시간) -> 활성(X시간) -> 죽음 이 세단계로 변한다.

    이 활성여부를 표시하기 위해 int isLive = -1:비활성, 1:활성 (죽었을때는 따로 표시하지 않았다. 큐에 안넣을거라서)

 - 생명력 : lifeTime / 지금까지 지난 시간 : nowTime

 

* 배열 크기

세포가 분포된 영역은 n * m이고, 위아래로 최대 k 까지 커질 수 있기 때문에

map의 크기는 [k * 2 + n][k * 2 + m]으로 잡았다.

사실 여유롭게 최대크기인 650으로 잡고 싶었지만 혹시나 터질까봐 무서워서 + 효율적으로 쓰고 싶은 마음에 딱 맞게 잡았다.

 

 

구현 방법

1. map을 입력받을 때, 세포가 있으면 전부 큐에 담는다.

 

2. k시간 뒤의 상태를 봐야하기 때문에, bfs는 while (!q.isEmpty)로 돌리는게 아니라 매 초마다 q.size() 만큼 돌린다.

 

3. 한군데에 중복으로 번식하면 더 생명력이 높은 세포를 살려야 하는데, 맵에 저장된 값과 지금 내가 들고있는 값이 다르면 버리게 했다.

 

4. 활성 상태이고 && 이제 갓 활성상태가 된 애들만 번식을 진행한다

문제를 잘 읽자

첫 1시간 동안이라는 말 놓치고 활성화된 내내 번식하는 줄 알고.. 삽질했다..ㅠㅠ 

 

5. 번식 코드를 짤 때 충돌에 관한 부분이 있는데, 만약 처음에 3짜리가 번식했는데 이후에 5짜리가 번식하는 경우가 있다. 이때는 5짜리만 남고 3짜리는 없애야 한다.

근데 이게 지금 이 순간에 둘다 번식한거면 이게 맞지만, 3짜리가 이전 시점에 번식한거면 3을 살려야 한다.

그래서.. 이부분 해결을 위해 map을 2차원으로 만들고 map[i][j][1] 여기에는 번식 시점을 기록했다.

지금 내가 심으려는 곳에 이미 심어져 있으면 -> 심어진 시점을 확인한다.

심어진 시점이 같으면 -> 크기 비교를 해서 맵에 남기고

심어진 시점이 다르면 -> 지금은 심지 않고 버린다.

 

6. nextTime이라는 변수(지금까지 지난 시간 + 1)를 만들어서, 다음 턴에 이 세포의 상태가 어떻게 변할지를 본다.

만약 nextTime == 생명력이면 다음턴에 상태가 변한다는건데

비활성이면 -> 활성 + 지금까지 지난 시간을 0으로 초기화해서 큐에 넣고

활성이면 -> 죽였다(아무것도 안함)

 

이 단계에서, 상태가 바뀌지는 않지만 시간만 1 증가하는 경우를 놓쳐서 큐에 안넣었더니

테케 3, 4가 0이 나왔다. 잘 확인하자.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Solution {
	
	private static class Node {
		int x, y, isLive, lifeTime, nowTime;
		Node(int x, int y, int isLive, int lifeTime, int nowTime) {
			this.x = x;
			this.y = y;
			this.isLive = isLive;	//비활성: -1, 활성: 1
			this.lifeTime = lifeTime;
			this.nowTime = nowTime;
		}
	}
	
	private static int n, m, k, map[][][];
	private static int[] dx = {0, -1, 0, 1}, dy = {-1, 0, 1, 0};
	private static Queue<Node> q = new LinkedList<>();

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			q.clear();
			
			st = new StringTokenizer(br.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			k = Integer.parseInt(st.nextToken());
			
			map = new int[k * 2 + n][k * 2 + m][2];
			for (int i = 0; i < n; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < m; j++) {
					map[k + i][k + j][0] = Integer.parseInt(st.nextToken());
					
					if (map[k + i][k + j][0] != 0)
						q.add(new Node(k + i, k + j, -1, map[k + i][k + j][0], 0));
				}
			}
			for (int i = 1; i <= k; i++)
				bfs(i);
			sb.append("#" + t + " " + overlapCheck() + "\n");
		}
		
		System.out.println(sb);
	}

	private static int overlapCheck() {
		int count = 0;
		while (!q.isEmpty()) {
			Node temp = q.poll();
			//중복되지 않은 애만 카운트한다
			if (temp.lifeTime == map[temp.x][temp.y][0]) count++; 
		}
		return count;
	}

	private static void bfs(int now) {
		int size = q.size();	//한 턴마다 돈다 
		for (int i = 0; i < size; i++) {
			Node temp = q.poll();
			int nextTime = temp.nowTime + 1;
			int nextLive;
			
			//내 자리에 다른애를 심었다면 얘는 버린다
			if (temp.lifeTime != map[temp.x][temp.y][0]) continue; 
			
			//번식부분. 활성상태면 사방으로 번식시킨다
			if (temp.isLive == 1 && temp.nowTime == 0) { 
				
				for (int d = 0; d < 4; d++) {
					int nx = temp.x + dx[d];
					int ny = temp.y + dy[d];
					
					//땅에 이미 다른애가 있는데
					if (map[nx][ny][0] != 0) {
						
						//예전에 번식한 경우에는 번식 X
						if (map[nx][ny][1] < now) {
							continue;			
						//이번에 번식한 애인데 
						} else if (map[nx][ny][1] == now) {
							//생명력이 내가 더 세다면 
							if (map[nx][ny][0] < temp.lifeTime) {
								map[nx][ny][0] = temp.lifeTime;
								q.add(new Node(nx, ny, -1, temp.lifeTime, 0));
							}
						}
					
					//아예 빈 땅이라면 그냥 심는다
					} else {
						map[nx][ny][0] = temp.lifeTime;
						map[nx][ny][1] = now;
						q.add(new Node(nx, ny, -1, temp.lifeTime, 0));
					}
				}
			} 
				
			//지금 내자신을 어떻게 할 지 
			//다음에 상태가 바뀔 애인데 
			if (nextTime == temp.lifeTime) {
				
				//지금 활성이면 다음에 죽을거니까 안넣음 
				if (temp.isLive == 1) {		
					continue;
				
				//지금 비활성이면 다음에 활성으로 바꿔서 큐에넣기
				} else if (temp.isLive == -1) {	 
					nextLive = 1;
					nextTime = 0;
					q.add(new Node(temp.x, temp.y, nextLive, temp.lifeTime, nextTime));
				}
		
			//상태가 바뀔 애가 아닐 때 
			} else {
				q.add(new Node(temp.x, temp.y, temp.isLive, temp.lifeTime, nextTime));
			}
		}
	}
}

 

삽질 포인트

1. 위에 썼던 '1시간 동안만 번식 진행' 놓쳐서 활성화 내내 번식되게 해서 삽질했다.

 

2. 나는 살아있는 세포 확인을 q.size()를 확인하는 방식으로 했는데,

큐에 충돌나서 원래는 없어야 하지만 들어가 있는 애들이 있다는 점을 간과했다.

bfs 코드에서는 분기문으로 걸러줬지만.. q.size()에서는 그게 없으니 계속 44/50개로 Fail 나와서 한시간동안 찾았다.

이걸 해결하기 위해서, k번만큼 bfs를 돌린 후에 overlapCheck()라는 함수를 만들어서 중복되는 애들을 걸러줬다.

논리적 허점이었다. 조금 더 논리력을 기르자.

 

끝!