SWEA 2382번: 미생물 격리

문제

문제 바로가기> SWEA 2382번: 미생물 격리

SW Expert Academy

 

 

풀이

.... 정말... 국어를 잘해야한다.

 

주의할 점

1. 군집이 동시에 움직인다. 처음에 번호순서대로 움직여서 답이 이상하게 나왔다 ^^,,

    이를 위해 tmpMap 배열을 이용해주었다!

2. "이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다."

    이 부분에서 구현 실수가 있었다. 

    예를 들어 군집 A=3, B=4, C=5라고 해보자.

     A, B, C 순서로 동일 칸에 도착했을 때, C의 방향이 해당 군집의 방향이 되어야 한다.

    그런데 만약 A < B 이니까, B의 크기를 7 로 저장을 해뒀다면??

    나중에 C가 왔을 때 ..... B가 크니까 내 방향이야!! 라고 해버릴 것 .....

    따라서 maxCnt 배열을 만들어서, 그 turn의 해당 위치에서 가장 큰 미생물 군집의 개수를 저장해주었다.

 

C++

#include<iostream>
#include<cstring>
#include<vector>
#define MAX 101
#define MAXK 1001
using namespace std;

struct MICROBE { 
	int y, x, cnt, dir;
	bool isdead = false;
};
vector<MICROBE> micorbe;

int N, M, K;
int map[MAX][MAX];
int tmpMap[MAX][MAX];
int maxCnt[MAX][MAX];
int dy[] = {-1, 1, 0, 0}; // 상: 1, 하: 2, 좌: 3, 우: 4
int dx[] = {0, 0, -1, 1}; // (-1 해서 idx 0 부터 사용)

void init() {
	micorbe.resize(MAXK);
	memset(map, 0, sizeof(map));
}

void input() {
	cin >> N >> M >> K;
	
	int y, x, cnt, dir;
	for (int n = 1; n <= K; n++) {
		cin >> y >> x >> cnt >> dir;
		map[y][x] = n;
		micorbe[n] = { y, x, cnt, dir-1, false };
	}
}

void move() {
	for (int n = 1; n <= K; n++) {
		if (micorbe[n].isdead) continue; // 합쳐졌거나, 사라진 군집인 경우
		
		int y = micorbe[n].y;
		int x = micorbe[n].x;
		int cnt = micorbe[n].cnt;
		int dir = micorbe[n].dir;

		int ny = y + dy[dir];
		int nx = x + dx[dir];

		if (ny == 0 || ny == N - 1 || nx == 0 || nx == N - 1) { // 약품이 칠해진 셀
			cnt /= 2; // 군집 내 미생물의 절반이 죽고,
			(dir == 0 || dir == 2) ? dir++ : dir--; // 이동방향이 반대로 바뀜
		}
		if (cnt == 0) { // 군집이 사라지는 경우
			micorbe[n].isdead = true;
			continue;
		}

		// 군집 정보 update
		micorbe[n] = { ny, nx, cnt, dir, false};
		
		if (tmpMap[ny][nx] == 0) {
			tmpMap[ny][nx] = n; // 비어 있는 경우
			maxCnt[ny][nx] = cnt;
		}
		else { // 두 개 이상의 군집이 한 셀에 모이는 경우 (군집이 합쳐짐)
			int on = tmpMap[ny][nx]; // 다른 군집 번호
			int oy = ny, ox = nx;
			int ocnt = micorbe[on].cnt;
			int odir = micorbe[on].dir;

			if (cnt < maxCnt[ny][nx]) { // 상대 군집의 미생물이 많은 경우
				micorbe[n].isdead = true;
				micorbe[on].cnt += cnt;
			}
			else { // 내 군집의 미생물이 많은 경우
				tmpMap[ny][nx] = n;
				maxCnt[ny][nx] = cnt;
				micorbe[on].isdead = true;
				micorbe[n].cnt += ocnt;
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if(tmpMap[i][j]) map[i][j] = tmpMap[i][j];
			else map[i][j] = 0;
			tmpMap[i][j] = 0;
			maxCnt[i][j] = 0;
		}
	}
}

void output(int t) { // M시간 후 남아 있는 미생물 수의 총 합
	int ans = 0;
	for (int n = 1; n <= K; n++) {
		if (micorbe[n].isdead) continue;
		ans += micorbe[n].cnt;
	}
	cout << "#" << t << " " << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		init();
		input();
		while (M--) move();
		output(t);
	}
}

 

Java

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

public class Solution {
	
	final static int[] dy = {-1, 1, 0, 0}; // 상 하 좌 우 	
	final static int[] dx = {0, 0, -1, 1};
	
	static int N, M, K;
	static int[][] map, tmpMap, maxCnt;
	static List<int[]> cluster; // 군집 정보 저장  (y, x, cnt, d, isdead)
	

	private static void move() {
		
		for(int k=1; k<=K; k++) {
			int isdead = cluster.get(k)[4];
			if(isdead == 1) continue;
				
			int y = cluster.get(k)[0];
			int x = cluster.get(k)[1];
			int cnt = cluster.get(k)[2];
			int d = cluster.get(k)[3];
			
			int ny = y+dy[d];
			int nx = x+dx[d];
			
			if(ny==0 || ny==N-1 || nx==0 || nx==N-1) { // 약품이 칠해진 셀에 도착
				if(d==0 || d==2) d++; //방향 변화 
				else d--;
				cnt/=2;
			}
			cluster.set(k, new int[] {ny, nx, cnt, d, 0});
			
			if(cnt == 0) {
				cluster.set(k, new int[] {0, 0, 0, 0, 1});
				continue;
			}
			
			if(tmpMap[ny][nx] == 0) { // 빈 칸 인 경우 
				maxCnt[ny][nx] = cnt;
				tmpMap[ny][nx] = k;
			}
			else { // 두개 이상의 군집이 한 셀에 모이는 경우 
				int other = tmpMap[ny][nx];
				int oy = cluster.get(other)[0];
				int ox = cluster.get(other)[1];
				int ocnt = cluster.get(other)[2];
				int od = cluster.get(other)[3];
				
				if(cnt < maxCnt[ny][nx]) {
					cluster.set(k, new int[] {0, 0, 0, 0, 1});
					cluster.set(other, new int[] {oy, ox, cnt+ocnt, od, 0});
				}
				else {
					cluster.set(other, new int[] {0, 0, 0, 0, 1});
					cluster.set(k, new int[] {ny, nx, cnt+ocnt, d, 0});
					maxCnt[ny][nx] = cnt;
					tmpMap[ny][nx] = k;
				}
			}
			
		}
		
		// copy 
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = tmpMap[i][j];
				tmpMap[i][j] = 0;
			}
		}
		
	}
	
	private static int output() {
		int ans = 0; // M시간 후 남아 있는 미생물 수의 총 합
		for(int i=0; i<cluster.size(); i++) {
			if(cluster.get(i)[4] == 1) continue;
			ans += cluster.get(i)[2];
		}
		return ans;
	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			tmpMap = new int[N][N];
			maxCnt = new int[N][N];
			cluster = new ArrayList<>();
			
			cluster.add(new int[] {0,0,0,0,1}); // dummy data ( for idx 1)
			for(int i=1; i<=K; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int y = Integer.parseInt(st.nextToken());
				int x = Integer.parseInt(st.nextToken());
				int cnt = Integer.parseInt(st.nextToken());
				int d = Integer.parseInt(st.nextToken()) - 1;
				cluster.add(new int[] {y, x, cnt, d, 0});
			}
			
			while(M-- > 0) move();
			sb.append("#"+t+" "+output()+"\n");
		}
		System.out.println(sb.toString());
	}

}