토마토_7576

시간초과가 나서 고심끝에 다른 이의 코드를 참조해,

arrayList -> Queue 로 바꿔줬더니 되었다.

 

그리고 더 간결한 코드를 위해 

ripen_tomato.get(0)을 매번 호출하는 다음 코드는 안좋은 코드다. 

public static void spread_rippen() {
		for (; ptr > 0  ; ptr--) {
			for (int i = 0; i < 4; i++) {
				if(ripen_tomato.get(0).x+row[i] < 0 || ripen_tomato.get(0).y+col[i] <0
				|| ripen_tomato.get(0).x+row[i] > a.length-1 || ripen_tomato.get(0).y+col[i]> a[0].length-1) continue;
				if(a[ripen_tomato.get(0).x+row[i]][ripen_tomato.get(0).y+col[i]]==0) {
					a[ripen_tomato.get(0).x+row[i]][ripen_tomato.get(0).y+col[i]]=1;
					ripen_tomato.add(new Dot(ripen_tomato.get(0).x+row[i],ripen_tomato.get(0).y+col[i]));
				}
			}
			ripen_tomato.remove(0); //삭제 
		}
	}

다음 과같이 Dot dot 객체를 생성해서 ripen_tomato.get(0)은 한번만 호출하면 코드도 더 깔끔하고, 호출횟수도 줄어들것이다!

public static void spread_rippen() {
		for (; ptr > 0  ; ptr--) {
			Dot dot= ripen_tomato.get(0);
			for (int i = 0; i < 4; i++) {
				if(dot.x+row[i] < 0 || dot.y+col[i] <0
				|| dot.x+row[i] > a.length-1 || dot.y+col[i]> a[0].length-1) continue;
				if(a[dot.x+row[i]][dot.y+col[i]]==0) {
					a[dot.x+row[i]][dot.y+col[i]]=1;
					ripen_tomato.add(new Dot(dot.x+row[i],dot.y+col[i]));
				}
			}
			ripen_tomato.remove(0); //삭제 
		}
	}

같은 맥락으로 

dot.x+row[i]를  int X =dot.x+row[i]로 하면 + 연산을 매번 안해도 된다. 

dot.x+col[i]를  int X =dot.x+col[i]로 하면 + 연산을 매번 안해도 된다. 

 

안좋은 코드 

for (int i = 0; i < 4; i++) {
				if(dot.x+row[i] < 0 || dot.y+col[i] <0
				|| dot.x+row[i] > a.length-1 || dot.y+col[i]> a[0].length-1) continue;
				if(a[dot.x+row[i]][dot.y+col[i]]==0) {
					a[dot.x+row[i]][dot.y+col[i]]=1;
					ripen_tomato.add(new Dot(dot.x+row[i],dot.y+col[i]));
				}
			}

개선된 코드

for (int i = 0; i < 4; i++) {
				int X =dot.x+row[i];
				int Y =dot.y+col[i];
				
				if(X < 0 || Y <0 || X > a.length-1 || Y> a[0].length-1) continue;
				
				if(a[X][Y]==0) {
					
					a[X][Y]=1;
					q.add(new Dot(X,Y));
					
				}
			}

 

내 코드

package study_IM;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;


class Dot {
	int x;
	int y;

	public Dot(int x,int y) { //생성자엔 void 안붙음 
		this.x=x;
		this.y=y;
	}
}

public class 토마토_7576 {
	
	static int ptr=1;
	static int a[][];
	static int row[]= {0,-1,0,1};
	static int col[]= {-1,0,1,0};
	static int count;
	public static void spread_rippen(Queue<Dot> q) {
		for (ptr=q.size(); ptr > 0; ptr--) {
			Dot dot=q.poll();
			for (int i = 0; i < 4; i++) {
				int X =dot.x+row[i];
				int Y =dot.y+col[i];
				
				if(X < 0 || Y <0 || X > a.length-1 || Y> a[0].length-1) continue;
                // 범위 구할땐 if(0 <= X && X <a.length && 0 <= Y && Y < a[0].length ) continue; 가 더 직관적이다. 
				
				if(a[X][Y]==0) {
					a[X][Y]=1;
					q.add(new Dot(X,Y));
				}
			}
		
		}// for ptr
			
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
		String read =in.readLine();
		String arr[] =read.split(" ");
		
		int N= Integer.parseInt(arr[0]);
		int M= Integer.parseInt(arr[1]);
		a =new int[M][N];
		Queue<Dot> q=new LinkedList();
	
		for (int i = 0; i < M; i++) {
			String read1[] =in.readLine().split(" ");
			
			for (int j = 0; j < N; j++) {
			
				a[i][j]=Integer.parseInt(read1[j]);
				
				if(a[i][j]==1) { //익은 토마토 기록 
					
					q.add(new Dot(i,j));
				}
			}
		} //for  n*m
		
		ptr=q.size();

		while(!q.isEmpty()) {
			spread_rippen(q);
			count++;
			
		}
		count--;
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(a[i][j]==0) { //안익은게 있다면
					count=-1;
					break;
				}
			}
			if(count==-1) {
				break;
			}
		} //for 
		
		System.out.println(count);

	}// main

}

 

문제푸는데 4시간걸렸다. 

1시간 풀기 

2시간 디버깅 (bufferreader 찾아보기, 로직이 맞았는데 시간초과 남, max가 1칸 더 나옴 그래서 최종값에 -1 하려는데 로직 새로 짜느라 오래걸림 )

1시간 arrayList -> Queue 로 바꾸는 인사이트 얻음