[백준 - 16235번] 나무 제테크- JAVA 정리 및 해설(삼성 SW 역량테스트)

안녕하세요. 이번에 풀어볼 문제는 나무 제테크입니다. 나무제테크는 시뮬레이션을 이용한 문제입니다. 

 

 

문제 자체는 엄청 간단하므로, 구현하라는 대로 구현을  해주면 그렇게 어려울게 없는 문제입니다만, 구현대로 하면 약간의 오류가 발생하는데요. 바로 시간초과에 걸리게됩니다.

 

처음에 문제를 풀때는  ArrayList를 이용해서 문제를 풀었는데 이 경우는 시간 초과가 발생하게 됩니다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
	static int n,m,k;
	static int map[][], sdmap[][];
	static int dx[] = {-1,-1,-1, 0,0 ,1,1,1};
	static int dy[] = {-1,0,1, -1,1, -1,0,1};
	public static ArrayList<tree> treeArray =new ArrayList<tree>() , deadTree=new ArrayList<tree>();
	

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer(tc," ");
		n = Integer.parseInt(st.nextToken()); //땅 크기 
		m = Integer.parseInt(st.nextToken()); //나무 갯수.
		k = Integer.parseInt(st.nextToken()); //몇년이 지났는지?
		sdmap = new int [n+2][n+2]; // 로봇이 양분을 줄 수 있는 지도..
		map = new int[n+2][n+2]; // 실제 땅의 양분을 표시하는 지도.
		for(int i=0; i<n+2; i++){
			Arrays.fill(sdmap[i], -1);
			Arrays.fill(map[i], -1);
		}
		for(int i =1; i<n+1; i++){
			String ms = br.readLine();
			st = new StringTokenizer(ms, " ");
			for(int j=1; j<n+1; j++){
				sdmap[i][j] = Integer.parseInt(st.nextToken());
				map[i][j] = 5; // 5로 고정.
			}
		} // 지도 양분 맵핑.
		for(int i=0; i<m; i++){
			String ts = br.readLine();
			st = new StringTokenizer(ts, " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			treeArray.add(new tree(x,y,z));
		}//나무배열에 새로운 나무 객체넣어 두기.
		k*=4; //4계절이니까 1년을 4배해서 분기별(봄,여름,가을,겨울)로 루틴 돌리기.
		Comparator<tree> treeComparator = new Comparator<tree>() { // 무조건 나이가 어린 순서대로 양분을 먹어야하므로 나이어린순서대로 sort할 수 있는 비교자 필요. 
            @Override
            public int compare(tree t1, tree t2) {
                return t1.year-t2.year;
            }
        };
		while(k>0){
			if(k%4==0){ //봄 
//				System.out.println("Spring");
				for(int i=0; i<treeArray.size(); i++){
					tree temp = treeArray.get(i);
					int x = temp.x;
					int y = temp.y;
					int year = temp.year;
					if(map[x][y]>= year){ // 실제 땅에 양분의 양이 자기 나이보다 많으면 양분빨아서 먹음.
						map[x][y] -= year;
						temp.year++;
					}
					else{ // 못먹으면 죽음. 
						deadTree.add(temp); //죽은 나무들은 죽은 나무끼리 모아주
						treeArray.remove(i); // 버려줌.
						i--; //단,링크드리스트기때문에 전체배열자체가 사이즈가 작아지고, i 위치도 조정필요.(전체에서 다빠지고, 한칸씩 밀리기때문에 인덱스도 빼줘야함.)
					}
				}
				/*for(int i=0; i<treeArray.size(); i++){
					tree temp = treeArray.get(i);
					System.out.println("남은거: "+temp.toString());
				}*/
				
			}
			else if(k%4==3){ // 여름.
//				System.out.println("summer");
				for(int i=0; i<deadTree.size(); i++){ // 죽은 나무들 위치에서 양분 주기.
					tree temp = deadTree.get(i);
					int addYear = temp.year/2;
					map[temp.x][temp.y] += addYear; 
					deadTree.remove(i);
					i--;
				}
			}
			else if(k%4==2){// 가을.
//				System.out.println("fall");
				for(int i=0; i<treeArray.size(); i++){
					tree temp = treeArray.get(i);
					int x = temp.x;
					int y = temp.y;
					int year = temp.year;
					if(year%5==0){ //5배수면 자기 주면여기저기에 나무뿌리기.
						for(int j=0; j<8; j++){
							if(map[x+dx[j]][y+dy[j]] != -1){
								treeArray.add(new tree(x+dx[j], y+dy[j] , 1)); //1짜리 새로운 
							}
						}
					}
				}
		        Collections.sort(treeArray, treeComparator); //나무어린 순서대로 정렬해주기. 그래야지 같은위치에 있더라도 양분 어린순서대로 먹음.
		      /*  for(int i=0; i<treeArray.size(); i++){
					tree temp = treeArray.get(i);
					System.out.println(temp.toString());
		        }*/
			}
			else{// 겨울. 
//				System.out.println("winter");
				for(int i =1; i<n+1; i++){ // S2D2가 양분 뿌리고 다니는것.
					for(int j=1; j<n+1; j++){
						map[i][j]+=sdmap[i][j]; 
					}
				}
			}
			k--;
		}
		bw.write(String.valueOf(treeArray.size()));
		bw.flush();
		bw.close();
	}

}
class tree{
	int x, y, year;
	public tree(int x, int y, int year){
		this.x=x;
		this.y=y;
		this.year=year;
	}
	public String toString(){
		return "tree's x: "+x+" y: "+y+" year: "+year;
		
	}
}

왜 이런 경우가 발생하는지 저도 정확하게 말씀은 못드리겠으나, 자바의 경우 0.3×2+1초 이므로 1.6초 안에 연산을 완성해야하는데, ArrayList로 할시 정렬 혹은, 그 node를 때고 붙히는 과정에서 시간적 지연이 있는것이 아닐까 추측해봅니다.

 

그 이후 가장 적합한 방법은 Deque(덱)을 이용해서 푸는 것이라고 생각했습니다. (사실은 덱으로 풀었다는 사람을 보고 막연하게 시도 해보았는데요.)

 

deque의 특성은 스택의 특성과 큐의 특성을 동시에 들고 있다는 조건을 가장 까다로운 조건을 해결해줄 것이라고 생각했습니다.

 

이문제에서 가장 까다로웠던 "나이가 어린 순서부터 양분을 먹는다" 를 해결하는데 있어서 덱은 Sort를 해주지 않는 방식을 통해 문제 해결 속도를 더 빠르게 진행할 수 있을 것 같다는 생각이 들었습니다.

 

덱은 첫번째로 순서대로 넣을 수도 있고 일부로 순서를 무시하고 앞부터 넣을 수도 있습니다.

나무들을 지니고 있는 덱(밑의 코드에서는 treeArray)에서 순서대로 넣게 된다면<꼬리로 삽입하기>(Queue의 특징) 자동적으로 머리부터 꼬리순서로 차곡차곡 쌓이게 됩니다. 

 

그렇다면 자동적으로 순서대로 빼서 양분을 먹고 나이를 먹어가면 결국 나이가 어린 것은 무조건 머리쪽에 나이가 많은 것은 꼬리쪽에 많을 것입니다. 

즉, 이점을 활용해서 나이가 어린 것을 머리부터 넣어버린다면, "나이가 어린 순서부터 양분을 먹는다" 를 위해서 굳이 정렬을 하지도 않고 문제를 해결 할 수 있습니다.

 

그런 방식을 통해서 해결한 코드입니다. 

 

/** 2019. 7. 18.
 * @author ventulus95
 * 내가 한 삽질 목록. 
 * 처음에 ArrayList했다가 시간초과뜸. -> deque로 변환해서 해봄. -> deque안에서 순서 꼬인거 모르고 mapping에러 확인해봄. 
 * -> 섞어서 쓰니까 문제 발생한거 인지 -> 고치고 맞춤.
 */
package codeBaekJoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.StringTokenizer;

public class No16235_treeMoneytech {
	static int n,m,k;
	static int map[][], sdmap[][];
	static int dx[] = {-1,-1,-1, 0,0 ,1,1,1};
	static int dy[] = {-1,0,1, -1,1, -1,0,1};
	static Deque<tree> treeArray =new ArrayDeque<tree>() , deadTree=new ArrayDeque<tree>();
	

	public static void main(String[] args) throws IOException {
	 	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		String tc = br.readLine();
		StringTokenizer st = new StringTokenizer(tc," ");
		n = Integer.parseInt(st.nextToken()); //땅 크기 
		m = Integer.parseInt(st.nextToken()); //나무 갯수.
		k = Integer.parseInt(st.nextToken()); //몇년이 지났는지?
		sdmap = new int [n+2][n+2]; // 로봇이 양분을 줄 수 있는 지도..
		map = new int[n+2][n+2]; // 실제 땅의 양분을 표시하는 지도.
		for(int i=0; i<n+2; i++){
			Arrays.fill(sdmap[i], -1);
			Arrays.fill(map[i], -1);
		}
		for(int i =1; i<n+1; i++){
			String ms = br.readLine();
			st = new StringTokenizer(ms, " ");
			for(int j=1; j<n+1; j++){
				sdmap[i][j] = Integer.parseInt(st.nextToken());
				map[i][j] = 5; // 5로 고정.
			}
		} // 지도 양분 맵핑.
		for(int i=0; i<m; i++){
			String ts = br.readLine();
			st = new StringTokenizer(ts, " ");
			int x= Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			int z = Integer.parseInt(st.nextToken());
			treeArray.add(new tree(y,x,z));
		}//나무배열에 새로운 나무 객체넣어 두기.
		k*=4; //4계절이니까 4배해서 분기별로 루틴 돌리기.
		while(k>0){
			if(k%4==0){ //봄 
//				System.out.println("Spring");
				Deque<tree> temptree = new ArrayDeque<tree>();
				while(!treeArray.isEmpty()){
					tree temp = treeArray.poll(); // 맨앞에서 빼고 시작. (순서대로 빼기.)
					int x = temp.x;
					int y = temp.y;
					int year = temp.year;
//					System.out.println("deque는 어케 되는가?: "+temp.toString());
					if(map[x][y]>= year){ // 실제 땅에 양분의 양이 자기 나이보다 많으면 양분빨아서 먹음.
						map[x][y] -= year;
						temp.year++;
						temptree.offer(temp); //temptree라는 덱에 빼낸 인자를 뒤로 넣기.(큐처럼 순서에 맞춰서 넣기.) 그래야지 순서 맞음.
					}
					else{ // 못먹으면 죽음. 
						deadTree.offer(temp); //죽은 나무들은 죽은 나무끼리 모아주기. 죽은건 순서 큰상관없음.
					}
				}
				treeArray = temptree; //빼낸 tree노드들을 treeArray에 붙혀 놓기.
				/*while(!treeArray.isEmpty()){
					tree temp = temptree.remove();
					System.out.println("남은거: "+temp.toString());
				}*/
			} 
			else if(k%4==3){ // 여름.
//				System.out.println("summer");
				while(!deadTree.isEmpty()){ // 죽은 나무들 위치에서 양분 주기.
					tree temp = deadTree.poll();
					int addYear = temp.year/2;
					map[temp.x][temp.y] += addYear; 
				}
			}
			else if(k%4==2){// 가을.
//			  	System.out.println("fall");
				Deque<tree> temptree = new ArrayDeque<tree>();
				while(!treeArray.isEmpty()){
					tree temp = treeArray.poll(); //앞에서빼도 상관없음. 예전처럼 뒤로 꼭 빼야되는 강박 없어도됨. 
					// 뒤로 빼야하는 강박이 있었던게 5의 배수부터 먼저빼야된다는 그런게 있어서 일부로 뒤로 빼고 싶었는데 생각하면, 순차적으로 앞으로 빼버려도 5의 배수로 가는데는 문제없음...
//					System.out.println("deque는 어케 되는가?: "+temp.toString());
					int x = temp.x;
					int y = temp.y;
					int year = temp.year;
					if(year%5==0){ //5배수면 자기 주면여기저기에 나무뿌리기.
						for(int j=0; j<8; j++){
							if(map[x+dx[j]][y+dy[j]] != -1){
								temptree.offerFirst(new tree(x+dx[j],y+dy[j], 1)); //1짜리 새로운 거 맨앞으로 넣기. 그래야지 나무가 나이순 정렬됨.
							}
						}
					}
					temptree.offer(temp); //그리고 남은거 뒤로 넣기.
				}
				treeArray=temptree;
				/*while(!treeArray.isEmpty()){
					tree temp = temptree.remove();
					System.out.println("남은거: "+temp.toString());
				}*/
			}
			else{// 겨울. 
//				System.out.println("winter");
				for(int i =1; i<n+1; i++){ // S2D2가 양분 뿌리고 다니는것.
					for(int j=1; j<n+1; j++){
						map[i][j]+=sdmap[i][j]; 
					}
				}
			}
			k--;
		}
		bw.write(String.valueOf(treeArray.size()));
		bw.flush();
		bw.close();
	}

}

class tree{
	int x, y, year;
	public tree(int x, int y, int year){
		this.x=x;
		this.y=y;
		this.year=year;
	}
	
	public String toString(){
		return "tree's x: "+x+" y: "+y+" year: "+year;
		
	}
}

 

 

자바에서 Deque를 쓸때 놓치지 말아야할 점. (너무 길어질 것 같아서 더보기로 달아둡니다)

부가적으로 제가 삽질한것 중 덱에서 발견한 특이한 것을 소개해드리자면, 

출처: 제타위키(https://zetawiki.com/wiki/%EC%9E%90%EB%B0%94_Deque)

덱에서 사용하는 명령어 모음인데, 

처음에는 덱에서 javadoc을 정확하게 안읽고 리턴값만 보고 "음.. 그렇군 이렇게 하면 뒤로 빠지고 저렇게하면 앞으로 빠지는구나" 이런식으로 진행했다가 망했는데요. 특히 이문제는 내가 어디서 잘못했는지를 찾기가 너무 까다로워서 처음에는 Mapping 실수라고 단정 지었습니다.

 

근데 알고보니까 deque의 순서가 꼬인 거더라구요. 왜 꼬였는지를 살펴보니까.

저는 특수값 메소드와 정상값 메소드를 섞어서 쓰고 있었습니다.  예를 들어 Poll()로 빼고 -> 넣을땐 add()로 넣는다던지

하지만 이러니까 deque에서 분명히 순서를 맞췄다고 생각했는데, 값이 예상과 다르게 섞이는 경우가 발생하더라구요.

 

즉, 이런 deque 문제를 해결 할때는 꼭 값별 메소드를 일치 시켜주는 과정을 꼭꼭꼭 지켜주십쇼

섞지 마세요..