[코드트리] 다수의 객체 이동

       문제 요약        

- 문제

https://www.codetree.ai/missions/2/problems/merge-marbles/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

         아이디어        

 

 

다음 판을 만들어야 함

다음 판에 데이터를 넣을 때, 그대로 일수도 있고 다음 위치일 수도 있고 

이런 조건을 잘 생각해야 함

 

1. 구슬 이동

2. 충돌 처리

3. 다음 준비

         소스코드        

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
	static int T; // 테스트케이스
	static int N, M; // 격자의 크기, 구슬의 개수
	static List<Item>[][] box;
	static int[][] way = {{-1,0},{0,1},{0,-1},{1,0}};

    public static void main(String[] args) throws Exception{
    	System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		T = Integer.parseInt(st.nextToken());
		
		box = initBox();
		for(int n = 1; n <= M; n++) {
			st = new StringTokenizer(br.readLine());
			int R = Integer.parseInt(st.nextToken()) - 1;
			int C = Integer.parseInt(st.nextToken()) - 1;
			int w = convertDir(st.nextToken().charAt(0));
			int weight = Integer.parseInt(st.nextToken());
			box[R][C].add(new Item(n, weight, w));
		}
		
		for(int time = 1; time <= T; time++) {
			List<Item>[][] nextBox = initBox();
			
			// 1. 구슬 이동
			for(int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if(box[i][j].size() > 0) {
						Item now = box[i][j].get(0);
						int nx = i + way[now.w][0];
						int ny = j + way[now.w][1];
						if(nx < 0 || nx >= N || ny < 0 || ny >= N) { // 방향을 바꾸는 데 1초 소요됨
							Item next = new Item(now.id, now.weight, 3 - now.w);
							nextBox[i][j].add(next); // 그대로 위치함
						} else {
							Item next = new Item(now.id, now.weight, now.w);
							nextBox[nx][ny].add(next); // 그곳으로 이동함
						}
						
					}
					
				}
				
			}
			//printBox(nextBox);

			
			// 2. 충돌 처리
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < N; j++) {
					if(nextBox[i][j].size() > 1) { // 충돌일어남
						List<Item> afterCrash = new ArrayList<>();
						int maxId = 0, maxW = 0, sumWeight = 0;
						for(int k = 0; k < nextBox[i][j].size(); k++) {
							sumWeight += nextBox[i][j].get(k).weight;
							if(maxId < nextBox[i][j].get(k).id) {
								maxId = nextBox[i][j].get(k).id;
								maxW = nextBox[i][j].get(k).w;
							}
						}
						afterCrash.add(new Item(maxId, sumWeight, maxW));
						nextBox[i][j] = afterCrash;
					}
				}
			}
			// 3. 다음 준비
			box = nextBox;

		}
		
		int cnt = 0;
		int maxWeight = 0;
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < N; j++) {
				List<Item> items = box[i][j];
				for(int k = 0; k < items.size(); k++) {
					maxWeight = Math.max(maxWeight, items.get(k).weight);
				}
				cnt += items.size();
			}
		}
		// 남아있는 구슬의 수| |"가장 무거운 구슬의 무게:
		System.out.println(cnt + " " + maxWeight);
	}
    
    static List<Item>[][] initBox(){
    	List<Item>[][] nextItems = new ArrayList[N][N];
    	for(int i = 0; i < N ; i++) {
    		for(int j = 0; j < N; j++) {
    			nextItems[i][j] = new ArrayList<>();
    		}
    	}
    	return nextItems;
    }
    
    // 무게가 가장 크거나, 무게가 같은 경우 구슬 번호
    static class Item implements Comparable<Item>{
    	int id, weight;
    	int  w;
    	Item(int id, int weight, int w){
    		this.id = id;
    		this.weight = weight;
    		this.w = w;
    	}
    
    	@Override
    	public int compareTo(Item o) {
    		if(o.weight == this.weight) {
    			return o.id - this.id;
    		}
    		return o.weight - this.weight;
    	}
    	@Override
    	public String toString() {
    		return "(" + this.id + ">> " + this.weight + ")";
    	}
    }

    static int convertDir(char x) {
    	if (x == 'U') {
    		return 0;
    	} else if (x == 'D') {
    		return 3;
    	} else if (x == 'R') {
    		return 1;
    	} 
    	return 2;
    }
    
   static void printBox(List<Item>[][] box) {
	   for(int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				System.out.print(box[i][j].toString());
			}
			System.out.println();
		}
	   System.out.println();
   }
}