[SWEA] 2382.미생물 격리 (java) / 시뮬레이션, BFS

@시뮬레이션, BFS / 3h (구현 1시간 디버깅 2시간)

처음 문제 읽으면서 낚시왕이랑 같은문제네 생각했고

문제 다 읽어보니 크게 어렵지 않을 것 같았는데

구현도 금방 했는데

디버깅 하다가 죽는 줄 알았다..

계속 테케 20개만 맞는다고 떠서... 질문 다 뒤져봐도 없고 울뻔..

겨우겨우 찾았다.

 

쉬운 문제처럼 보이는데 조건에 대한 로직을 잘 생각해야해서 약간 어려운 문제였다.

 

 

문제 링크

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

SW Expert Academy

 

 

구현 방법

1. 인덱스 처리

벽에 부딪히면 반대방향으로 방향을 바꿔야한다.

이걸 (기존방향 + 2) % 4 == 반대방향 이렇게 하기 위해서

상 0 / 좌 1 / 하 2 / 우 3 순으로 입력받았다.

 

2. map을 Node[][] 형으로 선언했다.

Node클래스에는 x좌표, y좌표, 현재미생물의 수, 현재 방향, 현재 시간, 지금까지 최대 미생물 수를 담는다.

이게 중요한게, 미생물 2개가 합쳐지는건 괜찮은데

만약 미생물이 2, 4, 5가 한군데에서 합쳐지는데 2, 4가 합쳐져서 6이 되버리면 5보다 커져서 방향이 꼬여버린다.

그래서 합칠 때 지금까지 합친 애들 중에서 가장 큰 미생물 수를 따로 갖고 있어야 한다.

 

3. 미생물이 합쳐졌을 때, 문제는 합쳐지기 전에 미리 이동한 미생물이 큐에 그대로 살아있게 된다.

이때는 큐에서 poll해왔을 때 그 애의 미생물 수와 맵에 저장된 미생물 수가 다르면 continue해서 버리는 방식으로 진행했다.

 

4. map을 두개 사용했다.

이동하는 과정에서 기존에 있는 아직 이동 안한 애와 충돌하는 경우가 있고, 이동해놓은 애와 충돌하는 경우가 있어서 두개를 번갈아가면서 prevMap, nowMap으로 이동하게끔 구현했다.

 

 

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, dir, time;
        long num, maxNum;
		public Node(long num, int dir, int time, long maxNum) {
			this.num = num;
			this.dir = dir;
			this.time = time;
			this.maxNum = maxNum;
		}
		public Node(int x, int y, long num, int dir, int time, long maxNum) {
			this.x = x;
			this.y = y;
			this.num = num;
			this.dir = dir;
			this.time = time;
			this.maxNum = maxNum;
		}
	}
	private static int N, M, K;
	private static Node[][] map1, map2;
	private static Queue<Node> q;
	private static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
	
	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++) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());

			q = new LinkedList<>();
			map1 = new Node[N][N];
			map2 = new Node[N][N];
			
			int a, b, c, d;
			for (int i = 0; i < K; i++) {
				st = new StringTokenizer(br.readLine());
				a = Integer.parseInt(st.nextToken());
				b = Integer.parseInt(st.nextToken());
				c = Integer.parseInt(st.nextToken());
				d = Integer.parseInt(st.nextToken());
				if (d == 1) d = 0;
				else if (d == 3) d = 1;
				else if (d == 4) d = 3;
				
				map1[a][b] = new Node(c, d, 0, c);
				q.add(new Node(a, b, c, d, 0, c));
			}
			move();
			sb.append("#" + t + " " + count() + "\n");
		}
		System.out.println(sb);
	}

	private static void move() {
		int nx, ny, ndir, ntime, idx = 0;
        long nnum, nmaxNum;
		Node[][] prevMap, nowMap;
		
		while (!q.isEmpty()) {
			if (idx % 2 == 0) {
				prevMap = map1;	nowMap = map2;
			} else {
				prevMap = map2; nowMap = map1;
			}
			
			int size = q.size();
			for (int i = 0; i < size; i++) {
				Node temp = q.poll();
				if (temp.time >= M) return;
				if (temp.num != prevMap[temp.x][temp.y].num) continue;
				
				prevMap[temp.x][temp.y] = null;
				
				nx = temp.x + dx[temp.dir];
				ny = temp.y + dy[temp.dir];
				nnum = temp.num;
				ndir = temp.dir;
				ntime = temp.time + 1;
				nmaxNum = temp.maxNum;
				
				//벽에 부딪힌 경우 
				if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1) {
					ndir = (ndir + 2) % 4;
					nnum = nnum / 2;
					nmaxNum = nnum;
					if (nnum == 0) continue;
	
				//움직이려는 자리에 이미 누군가가 있는 경우 
				} else if (nowMap[nx][ny] != null) {
					//원래 군집 애가 더 크다면 
					//이때는 maxNum 아래처럼 안 해줘도 되는게, 어차피 지금 가진 num과 비교하기 때문에 상관없다!
					if (nowMap[nx][ny].maxNum > nnum) {
						ndir = nowMap[nx][ny].dir;
						nmaxNum = nowMap[nx][ny].maxNum;
					}
					nnum += nowMap[nx][ny].num;
				} else {	//아무것도 없는 맵에 넣어 줄 때는 maxNum을 꼭 갱신해줘야 한다!!! 이것때매 삽질함 ㅠㅠ 
					nmaxNum = nnum;
				}
				nowMap[nx][ny] = new Node(nnum, ndir, ntime, nmaxNum);
				q.add(new Node(nx, ny, nnum, ndir, ntime, nmaxNum));
			}
			idx++;
		}
	}
	
	private static long count() {
		Node[][] map;
		if (M % 2 == 0) map = map1;
		else map = map2;
		
		long count = 0;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				if (map[i][j] != null)
					count += map[i][j].num;
		
		return count;
	}
}

 

 

삽질 포인트

1. 테스트케이스 20개만 맞을 때의 문제점을 아무리 찾아도 찾을 수가 없었다.

겨우 찾고 보니 2, 4, 5 미생물이 합쳐지면 현재미생물의 수는 11로 제대로 들어가는데 최대미생물 수가 합쳐지기 전의 최대값인 5로 들어가 있어서 다음 턴에 문제가 발생했다. 그래서 다음 턴에서 처음으로 맵에 넣어줄 때 지금까지의 최대 미생물 수를 현재 미생물 수로 업데이트 해 줬다.

+ 다음 턴에 이미 다른 미생물이 있는 자리에 또 넣을 경우에는 안 해도 된다. 왜냐하면 그 때는 어차피 지금 들고있는 미생물 수와 비교하기 때문에 최대 미생물 수는 의미가 없기 때문이다.

 

이것때문에 머리 터지는 줄 알았다 ㅠㅠ

 

2. 시간별로 이동시켜야 해서 q.size만큼 for문을 돌렸는데(아기상어와 비슷한 느낌),

for문 안에서 큐 사이즈가 계속 변하는데, 그걸 깜빡하고 for문의 조건문에 i < q.size()로 해놔서 계속 말도 안되는 값이 나왔다.

q.size()로 for문을 돌릴 때는 꼭! int size = q.size(); 로 값을 빼놓고 size만큼 돌릴 것!

 

 

요새 시뮬 풀 때 구현은 금방 하는데, 디버깅에서 시간이 2시간씩 걸린다.

코드 짜기 전에 로직을 조금 더 탄탄히 짜는 연습을 해야겠다.

 

끝!