[SWEA] 2382. 미생물 격리 (D0^ / 시뮬레이션) - Java

링크

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

SW Expert Academy

 

 

 

 

문제 해석

- 문제 분석
미생물이 크기와 방향을 가진 채 존재
미생물은 매초마다 한 칸씩 이동
미생물이 이동하는 구역의 외곽에는 약품으로 처리되어 있어 미생물 크기를 반감시킴 (소수점이 나오면 내림 처리)

미생물이 한 칸에 모이는 경우 미생물이 합쳐지며, 이 때 가장 큰 미생물의 방향을 적용시킴


- 입력
첫 번째 줄 : N M K  # N=맵크기 | M=시간 | K=미생물개수
나머지 줄  : a b c d  # (미생물의) 세로, 가로, 미생물수, 이동방향 

 

- 출력
M시간이 지난 후 구역에 남아있는 미생물의 총합

 

 

 

 

풀이 & 코드 해석

- 문제 풀이
해당 문제는 시뮬레이션 문제로 분류됩니다.

이 문제에서 중요하게 고려해야 할 포인트는 미생물을 합치는 방법과, 미생물이 합쳐질 때 어떤 방향을 잡을 것인가 라고 생각됩니다.

1)

Fig 2

먼저 Fig2의 G,H에서 알 수 있듯이 미생물이 정확히 한 포인트에 만날 때 미생물들이 합쳐집니다.

 

Fig 3

만약 미생물들이 Fig3의 A,B처럼 서로 마주치지만 같은 포인트에서 만나지 않는다면 서로 지나치게 됩니다. (합쳐지지 않습니다)

2) 
Fig2의 D,F,E처럼 한 포인트로 여러 미생물이 이동하는 경우 가장 높은 숫자의 방향으로 정해지게 됩니다.


- 코드 해석
위에서 나온 1)의 문제를 해결하기 위해서 매 반복마다 map을 초기화하고, 미생물이 이동할 때마다 결과를 map에 저장하였습니다.

2)는 PriorityQueue를 이용하여 size가 큰 순서대로 비교를 시켰습니다.

 

 

 

코드

package day07;

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

public class 미생물격리 {

	static int N, M, K, answer;
	static Point[][] map;
	static PriorityQueue<Point> q;

	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	static class Point implements Comparable<Point> {
		int x;
		int y;
		int size;
		int rot;
		int level;

		Point(int x, int y, int size, int rot, int level) {
			this.x = x;
			this.y = y;
			this.size = size;
			this.rot = rot;
			this.level = level;
		}

		@Override
		public int compareTo(Point o) {
			return o.size - this.size;
		}
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		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()); // 미생물 개수

			answer = 0;
			map = new Point[N][N];
			q = new PriorityQueue<>();
//			print(map);

			for (int i = 0; i < K; i++) {
				// 나머지 줄
				st = new StringTokenizer(br.readLine());
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				int size = Integer.parseInt(st.nextToken());
				int rot = Integer.parseInt(st.nextToken()) - 1; // 0부터 시작을 위해
				q.offer(new Point(x, y, size, rot, 0));
			}

			bfs();

			System.out.println("#" + test_case + " " + answer);

		} // [E] test_case
	}

	private static void print(Point[][] map) {
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
	}

	private static void bfs() {
		while (!q.isEmpty()) {
			Point p = q.poll();

			// 시간이 모두 지나면 종료
			if (p.level == M) {
				answer += p.size;

				while (!q.isEmpty()) {
					p = q.poll();
					answer += p.size;
				}

				return;
			}

			int nx = p.x + dx[p.rot];
			int ny = p.y + dy[p.rot];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
				// 가장자리라면
				if (nx == 0 || nx == N - 1 || ny == 0 || ny == N - 1) {
					p.size = p.size / 2; // 사이즈를 반으로 만듦

					if (p.rot == 0) { // 회전
						p.rot = 1;
					} else if (p.rot == 1) {
						p.rot = 0;
					} else if (p.rot == 2) {
						p.rot = 3;
					} else if (p.rot == 3) {
						p.rot = 2;
					}
				}

				Point before = map[nx][ny];
				// 맵에 기존 값이 존재한다면 값을 비교
				if (before != null) {
					// 현재 값이 더 크다면
					if (before.size < p.size) {
						before.rot = p.rot;
					}
					before.size += p.size;

				}
				// 맵에 기존 값이 존재하지 않는다면
				else {
					map[nx][ny] = new Point(nx, ny, p.size, p.rot, p.level + 1);
				}
			}
		} // [E] q while

		// 모든 미생물 처리가 끝나면 맵을 탐색하여 미생물을 q에 저장
		for (int i = 0; i < map.length; i++) {
			for (int j = 0; j < map[i].length; j++) {
				if (map[i][j] != null) {
					q.offer(map[i][j]);
				}
			}
		}

		// map 초기화
		map = new Point[N][N];
		bfs();
	}
}

 

 

 

 

발생한 문제 & 해결 방안

처음 코드에서 테스트 케이스 중 3번과 7번을 틀리고, 최종적으로 전체 50개 중 42개가 맞았다.

해당 코드에서 발생한 문제는 문제 풀이에서 나온 2)를 고려하지 않았다는 점이다.

만약 3 5 7이 한 포인트로 이동한다고 가정했을 때 7이 가장 높은 값이므로 7의 방향으로 이동해야 하지만, 만약 3과 5를 먼저 연산하면 7보다 큰 8이 새롭게 나타나기 때문에 결론적으로 5의 이동방향이 전체 미생물의 이동방향이 되는 문제가 있다.

 

PriorityQueue를 정확히 이해하자!!!!!!!!

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java