[백준] 7569 토마토 - JAVA

출처 - 백준 알고리즘

7569번: 토마토

---

알고리즘 

• 3차원 배열을 사용해서 접근하는 문제 
• 6방향으로 토마토를 익게 할 수 있으며, 토마토가 비어있는 경우에는 익지 않는다. 
• 한번 익은 토마토는 다시 익지 않기 때문에 익은 토마토를 1로 바꿔주면, 방문처리는 따로 해주지 않아도 된다. 
• 각 날짜에 (방금 막)익은 토마토를 큐에 넣어서 다음 날 큐에 있는 토마토를 기준으로 6방향에 인접해 있는 토마토들을 익힌다.

---

 

구현 과정

• tomato[][][] : 창고에 보관되어 있는 토마토들의 상태를 저장한 배열 
• Queue<Tomato> start : 바로 전날 익은 토마토들을 담고 있는 큐, 하루마다 큐에 들어있는 토마토를 기준으로 6방탐색
• time : 토마토가 모두 익는데 걸리는 시간 

 

1. 처음 주어진 토마토의 상태를 tomato 배열에 저장하고, 만약 익은 토마토(=1) 가 있다면 start 큐에 넣는다. 

 

2. start 큐에 있는 토마토들을 하나씩 꺼내며 6방향으로 토마토를 익힌다. 

 

3. 만약 창고의 경계를 벗어나거나, 이미 익은 토마토(=1) 또는 비어 있는 창고 (=-1) 일 경우 다음 방향 탐색, continue 

 

4. 그렇지 않을 경우 토마토를 익히고, (1로 변경)  방금 익힌 토마토를 start 큐에 넣는다. 

 

5. 하루동안 익힐 수 있는 토마토를 모두 익혔다면 time ++ 후,  2~ 과정을 반복한다. 

 

6. 만약 모든 토마토가 익었다면 time을 리턴한다.

 

7. 모든 토마토가 익지 않았는데 start 큐가 비어있다면, 더 이상 익힐 수 있는 토마토가 없기 때문에 -1 를 출력한다. 

---

 

소스 코드

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

public class Solution_BaekJoon_7569 {
	static int N,M,H; 
	static int tomato[][][];
	static Queue<Tomato> start= new LinkedList<>(); 
	static class Tomato{
		int h; int x; int y;
		public Tomato(int h, int x, int y) {
			this.h=h;
			this.x=x;
			this.y=y; 
		}
	}
    
	public static void main(String[] args) throws Exception {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st;
		 
		st = new StringTokenizer(br.readLine(), " "); 
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		H = Integer.parseInt(st.nextToken());
		
		tomato= new int[H][N][M]; 
		
		for(int a=0; a<H; a++) {
			for(int b=0; b<N; b++) {
				st= new StringTokenizer(br.readLine(), " "); 
				for(int c=0; c<M; c++) {
					tomato[a][b][c]= Integer.parseInt(st.nextToken());
					if(tomato[a][b][c]==1) {
						start.add(new Tomato(a, b, c)); 
					}
				}
			}
		}
        
		System.out.println(riped());		
	}//end of main 
	
	private static int dx[]= {-1,1,0,0,0,0};
	private static int dy[]= {0,0,-1,1,0,0};
	private static int dz[]= {0,0,0,0,-1,1}; 
	
	//토마토 익기 
	private static int riped() {
		int time=0; 
		while(true) {
			if(isEnd()) return time; //모든 토마토가 익음 
			int size= start.size(); 
			if(size ==0 ) break; 
			for(int i=0; i<size; i++) {
				Tomato t= start.poll(); 
				int h= t.h;
				int x= t.x;
				int y= t.y;
				
				for(int dir= 0; dir<6; dir++) {
					int nh= h+dz[dir];
					int nx= x+dx[dir];
					int ny= y+dy[dir];
					
					if(isOut(nh, nx, ny) || tomato[nh][nx][ny] != 0) continue; 
					
					tomato[nh][nx][ny] = 1;
					start.add(new Tomato(nh, nx, ny)); 
				}
			}
			time++;
		}
		return -1; 
	}
    /*모든 토마토가 익었는지 검사*/
	private static boolean isEnd() {
		for(int a=0; a<H; a++) {
			for(int b=0; b<N; b++) {
				for(int c=0; c<M; c++) {
					if(tomato[a][b][c] == 0) return false; //안익은 토마토 있음 
				}
			}
		}
		return true; 
	}
	/*창고 경계 밖으로 빠져 나가는지 검사*/
	private static boolean isOut(int h ,int x, int y) {
		return h<0 || h>=H || x<0 || x>=N || y<0 || y>=M; 
	}
	
}//end of class

 

---

+ 위 문제는 3차원 배열로 접근하는건데, 똑같은 문제에 2차원 배열로 풀 수 있는 문제가 있다!! 

로직은 똑같이 하고, 2차원 배열로 풀이하면 쉽게 풀 수 있다. 

7576번: 토마토

---

소스 코드

import java.util.*;
import java.io.*;
public class Solution_BaekJoon_7576 {
	private static int dx[] = {-1,1,0,0};
	private static int dy[] = {0,0,-1,1};
	
	private static int N,M;
	private static int tomato[][]; 
	private static Queue<int[]> start= new LinkedList<>(); 
	
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in)); 
		StringTokenizer st; 
		
		st= new StringTokenizer(br.readLine(), " ");
		M=Integer.parseInt(st.nextToken());
		N=Integer.parseInt(st.nextToken());
		tomato= new int[N][M]; 
		
		for(int i=0; i<N; i++) {
			st= new StringTokenizer(br.readLine(), " ") ;
			for(int j=0; j<M; j++) {
				tomato[i][j]= Integer.parseInt(st.nextToken());
				if(tomato[i][j]==1) start.add(new int[] {i,j}); 
			}
		}
		
		System.out.println(riped());
	
	}//end of main 
	private static int riped() {
		int time=0; 
		while(true) {
			if(isEnd()) return time; //처음부터 다 익었으면 바로 0, 중간에 다 익었으면 return 
			int size= start.size();
			
			if(size==0) break; 
			for(int i=0; i<size; i++) {
				int[] a = start.poll(); 
				int x= a[0];
				int y= a[1];
				
				for(int dir=0; dir<4; dir++) {
					int nx= x+dx[dir];
					int ny= y+dy[dir];
					
					//경계 밖, 익었거나 없거나 
					if(isOut(nx, ny) || tomato[nx][ny] !=0) continue;
					
					tomato[nx][ny]=1;
					start.add(new int[]{nx,ny});
				}
			}
			time++;	
		}
		return -1; 
	}
	
	private static boolean isEnd() {
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(tomato[i][j]==0) return false; //안익은 토마토 남았음 
			}
		}
		return true; 
	}
	
	private static boolean isOut(int x, int y) {
		return x<0 || x>=N || y<0 || y>=M; 
	}
}//end of class