[JAVA] SWEA 2382 미생물 격리

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

SW Expert Academy

 

1. 서론

 

이 문제는 아마 전에 이런 문제를 풀어본 적이 있냐, 없냐에 따라 난이도가 갈릴 것 같다. 나는 이런 문제를 꽤 풀어봐서 익숙했다. 그래서 모의 SW 역량 테스트지만 디버깅 한 번 없이, 중간에 찍어보거나 하지도 않고 그냥 0부터 끝까지 짜고 돌렸더니 1트만에 맞았다...

이 문제들의 공통점은 전부 삼성 관련 기출이라는 것과 2차원 배열에서 직접 움직이지 않고 주어진 리스트 내에서 좌표값만 바꿔주는 식으로 푸는 문제라는 것이다. 처음 접했을 땐 한 좌표에 여러 개의 값을 도대체 어떻게 처리하나 싶었는데 풀다보면 알 수 있다.

 

- 비슷한 문제 리스트

 

백준 20056 마법사 상어와 파이어볼

https://www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

 

Codetree 코드트리 싸움땅

https://www.codetree.ai/frequent-problems/battle-ground/description

코드트리

 

2. 문제 풀이

 

대충 문제를 요약하면 다음과 같다.

 

NxN 배열, 바깥쪽 가장자리에는 특수한 약품이 칠해져 있음
1시간마다 각자 이동방향에 있는 셀로 이동

약품이 칠해진 셀에 도착하면 군집 내 미생물 / 2, 이동방향이 반대로 바뀜
미생물 수가 0이 되면 군집이 사라지게 됨

이동 후 두 개 이상의 군집이 한 셀에 모이는 경우 군집들이 합쳐지게 된다
합쳐진 군집의 미생물 수 = 군집들의 미생물 수의 합
이동방향 = 미생물수가 가장 많은 군집의 이동방향
(합쳐지는 군집의 미생물 수가 같은 경우는 주어지지 않으므로 고려하지 않아도 됨)

구해야 하는 것: M 시간 후 남아있는 미생물의 총합

 

나는 문제를 이렇게 풀었다.

맵: 리스트 형태의 2차원 배열

큐: 문제에서 주어지는 군집 리스트

 

1) 좌표 이동

=> 약품이 칠해진 셀인 경우, 미생물/2가 0보다 크다면

계산한 값으로 큐에 넣음

=> 0인 경우 큐에서 빼고 다시 넣지 않는다.

아닌 경우 => 좌표만 이동

이동한 좌표의 흔적은 지워줌

 

2) 같은 좌표에 2개 이상 있는 경우 계산

 

포인트는 한 좌표에 여러 개의 값들을 어떻게 처리할 것이냐인데 나는 List형태의 2차원 배열을 만들었다. 파이어볼에서 문제에서는 그렇게 하지 않았지만 이렇게 하는 게 간편하고 쉬워 보여서 이걸 선택했다.

 

예를 들어 1,1이라는 좌표에 1,2,3 군집이 모였다면

map[1][1].add(1);

map[1][1].add(2);

map[1][1].add(3);

이런 식으로 넣어서 1,1이라는 좌표에 구별 값 1,2,3을 넣어 체크하는 방식으로 만들었다.

 

그럼 이때 map[1][1].size() > 1 이기 때문에 이 값을 계산해야 한다.

난 큐를 돌면서 큐를 넣었다 빼며 map[1][1]에 적힌 index값을 찾아서 만약 같은 값이 나온 경우

=> 합치기 위해 합계산, 방향을 위한 가장 큰 수 찾기 위해 if문 작성

아닌 경우

=> 다시 큐에 넣음

(이때 큐에 넣고 빼고 난리 부르스 안 하고 싶으면 class 정의할 때 comparable로 정렬 순위 정해놓으면 정렬 편하게 돌려서 값 구할 수 있음, 근데 귀찮아서 구현 안 함)

 

이를 통해 같은 값인 경우에는 큐에 다시 넣지 않음으로써 값을 제거하고 map에서도 값을 제거하고 합친 새로 만든 군집을 큐, 맵에 각각 배치했다.

 

3. 코드 설명

 

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


public class Solution {
	
	static int n, m, k;
	static List<Integer>[][] map;
	static Queue<Info> q;
	static int[] dx = {0, -1, 1, 0, 0}, dy = {0, 0, 0, -1, 1}; //상하좌우

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int t = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= t; tc++) {
        	StringTokenizer st = new StringTokenizer(br.readLine());
        	n = Integer.parseInt(st.nextToken());
        	m = Integer.parseInt(st.nextToken());
        	k = Integer.parseInt(st.nextToken());
        	
        	map = new ArrayList[n][n]; //군집이 어느 좌표에 있는가 체크, 한 좌표에 여러 개가 있을 수 있기 때문에 List
        	for (int i = 0; i < n; i++)
        		for (int j = 0; j < n; j++)
        			map[i][j] = new ArrayList<>();
        	
        	q = new ArrayDeque<>(); //군집 리스트 저장
        	for (int i = 1; i <= k; i++) {
        		st = new StringTokenizer(br.readLine());
        		int x = Integer.parseInt(st.nextToken());
        		int y = Integer.parseInt(st.nextToken());
        		int cnt = Integer.parseInt(st.nextToken());
        		int d = Integer.parseInt(st.nextToken());
        		q.add(new Info(i, x, y, cnt, d));
        		map[x][y].add(i);
        	}
        	
        	for (int i = 0; i < m; i++) {
        		move(); //군집 이동
        		calc(); //같은 좌표 계산
        	}
        	
        	int ans = 0;
        	while(!q.isEmpty())//모든 미생물의 합
        		ans += q.poll().cnt;
        	
        	sb.append("#" + tc + " " + ans + "\n");
        }
        bw.write(sb.toString());
        bw.close(); br.close();
    }
    
    public static void calc() { //같은 좌표에 2개 이상 있는 값 처리
    	for (int i = 0; i < n; i++) {
    		for (int j = 0; j < n; j++) {
    			if (map[i][j].size() > 1) { //2개 이상이면
    				int sum = 0, d = 0, tidx = 0, max = 0;
    				for (int w = 0; w < map[i][j].size(); w++) {
    					while (!q.isEmpty()) {
	    					Info t = q.poll(); //큐에서 하나씩 빼서 찾기
	    					if (t.idx == map[i][j].get(w)) {
	    						sum += t.cnt; //합 계산
	    						if (max < t.cnt) {
	    							max = t.cnt;
	    							tidx = t.idx;
	    							d = t.d;
	    						}
	    						break;
	    					}
	    					else
	    						q.add(t); //아니면 다시 넣음
    					}	
    				}
    				//합쳐서 하나로 만들어서 넣음
    				q.add(new Info(tidx, i, j, sum, d));
    				map[i][j].clear();
    				map[i][j].add(tidx);
    			}
    		}
    	}
    }
    
    public static void move() { //군집 이동
    	int size = q.size();
    	for (int i = 0; i < size; i++) {
    		Info t = q.poll();
    		int nx = t.x + dx[t.d], ny = t.y + dy[t.d];
    		int ck = range(nx, ny);
    		
    		if (ck == 1 && t.cnt / 2 > 0) //빨간 셀에 닿은 경우
    			q.add(new Info(t.idx, nx, ny, t.cnt / 2, change(t.d)));
    		if (ck == 0) //그 외에 범위 안에 있는 경우
    			q.add(new Info(t.idx, nx, ny, t.cnt, t.d));
    		
    		if ((ck == 1 && t.cnt / 2 > 0) || ck == 0) //만약 미생물 / 2가 0보다 작으면 그냥 없앰
    			map[nx][ny].add(t.idx);
    		
    		if (map[t.x][t.y].size() == 1) //좌표에 한 개인 경우
    			map[t.x][t.y].remove(0);
    		else { //좌표에 여러 개의 값이 있는 경우, 이동 전 좌표만 삭제
    			for (int j = 0; j < map[t.x][t.y].size(); j++) {
    				if (map[t.x][t.y].get(j) == t.idx) {
    					map[t.x][t.y].remove(j);
    					break;
    				}
    			}
    		}
    	}	
    }
    
    public static int change(int d) { //빨간 셀에 닿았을 때 방향 바꿔줌
    	if (d == 1) return 2;
    	if (d == 2) return 1;
    	if (d == 3) return 4;
    	if (d == 4) return 3; 
    	return 0;
    }
    
    public static int range(int nx, int ny) { //범위체크
    	if (nx == 0 || nx == n - 1 || ny == 0 || ny == n - 1) return 1; //빨간
    	if (nx >= 0 && nx < n && ny >= 0 && ny < n) return 0; //범위 
    	return -1; //범위 밖
    }
}
class Info {
	int idx, x, y, cnt, d; //번호, 좌표, 미생물 수, 이동방향
	
	public Info(int idx, int x, int y, int cnt, int d) {
		this.idx = idx;
		this.x = x;
		this.y = y;
		this.cnt = cnt;
		this.d = d;
	}
}

 

설명은 위의 문제와 자세하게 써놓은 주석 참조^^