[백준 - Java] 7576번 : 토마토

문제

www.acmicpc.net/problem/7576

7576번: 토마토

 

---

주요 변수 설명 

int[][] map : N * M의 2차원 배열을 만들어 토마토의 정보를 저장한다.

 

int mapCount = (N*M) - 빈칸의 총 개수 : 모든 토마토가 익었나 확인을 하기 위해, 전체 공간의 개수를 파악해놓는다.

 

int ripenedCount : 익은 토마토의 총 개수 

 

int day : 익을 때 까지의 날짜 

 

ArrayList<Point> ripenedTomato : 매번 익은 토마토의 위치를 찾는 번거로움을 없애기 위해 List에 익은 토마토의 좌표를 저장한다.

 

int index = 0 : 토마토 익히기 부분에서, 이미 다른 안 익은 토마토에 영향을 준 토마토를 제외하기 위해 사용 

 

int[] dx = {-1, 0, 1, 0}
int[] dy = {0, -1, 0, 1} : 상 - 좌 - 하 - 우 인접한 토마토 좌표 찾기에 이용되는 배열 

 

---

출력 조건

1. 저장될 때부터 모든 토마토가 익어있는 상태 : 0 출력

ripenedCount가 mapCount와 같은 경우 

 

2-1. 토마토가 모두 익음 : 모두 익을 때까지의 최소 날짜 출력

> 익힌 결과, 익은 토마토의 개수 ripenedCount가 mapCount와 같은 경우 

 

2-2. 모두 익지 못하는 상황이면 : -1 출력

> 익힌 결과, 익히기 전의 ripenedCount와 같은 경우 

 

if(ripenedCount == mapCount) { // 처음부터 토마토가 다 익어있는 경우 
	System.out.println(0);
} else {
	while(true) {
		int beforeSize = ripenedCount; // 익은게 있는지 확인을 위해 이전 ripenedCount 저장 

		ripen(map); // 토마토 익히기 

		if(ripenedCount == mapCount) { // 익힌 결과, 모든 토마토가 익은 경우 
			System.out.println(day);
			break;
		} else if(ripenedCount == beforeSize) { // 익히고 난 뒤에도 이전 사이즈와 동일하다면 모두 익지 못하는 상황 
			System.out.println(-1);
			break;
		}
	}
}

 

---

토마토 익히기

BFS를 이용해 익힌 토마토의 인접한 토마토들을 익혀준다.

BFS 한번이 하루가 지나는 것과 같다. 따라서 모든 BFS가 끝나면 day+1.

 

큐에 ripenedTomato 리스트에 있는 익은 토마토들을 넣어준다.

 

* 이전에 확인한 익은 토마토들은 배제시키기 위해 ripenedTomato에서 remove해주면 시간 초과 난다!

삭제할 토마토를 찾고, 삭제하고, 다시 나머지 토마토들의 자리를 이동해주는 과정이 오래 걸림

 

그래서 index 변수로 몇 번째 익은 토마토까지 확인했는지를 저장해주고, index번째의 익은 토마토부터 BFS를 해준다.

 

BFS를 수행하며 상하좌우 확인을 위해 dx, dy 배열로 좌표를 이동시키며 , 경계를 넘지 않는 안 익은 토마토를 찾는다.

 

*dx, dy BFS에 대해 더 자세히 알고 싶다면 아래 '연구소' 포스팅의 '이차원 배열에서 상하좌우 이동 팁!' 부분을 참고해주세요.

 

[백준 - Java] 14502번 : 연구소

 

// 토마토 익히기 
public static void ripen(int[][] map) {
	Queue<Point> queue = new LinkedList<>();

	/*		
		// remove하면 시간 초과 남. index 변수 만들어서 새로 들어온 익은 토마토부터 큐에 넣도록 함  
		while(!ripenedTomato.isEmpty()) { // 이미 익어있는 토마토들을 큐에 넣고 BFS 
			queue.add(ripenedTomato.get(0));
			ripenedTomato.remove(0); // 큐에 넣었다면 그 이후로는 확인할 필요 없으니 ripenedTomato 리스트에서 삭제 
		}
	 */

	for(int i = index; i < ripenedTomato.size(); i++) {
		queue.add(ripenedTomato.get(i));
	}
	index = ripenedTomato.size();

	while(!queue.isEmpty()) {
		int x = queue.peek().x;
		int y = queue.poll().y;

		for(int i = 0; i < 4; i++) { // 상 하 좌 우 이동 
			int nx = x + dx[i];
			int ny = y + dy[i];

			if(nx < 0 || ny < 0 || nx >= N || ny >= M) // 범위 벗어나면 pass 
				continue;

			if(map[nx][ny] == 0) { // 이동한 곳에 익지 않은 토마토가 있다면 
				map[nx][ny] = 1; // 익히고 익은 ripenedTomato 리스트에 추가 
				ripenedTomato.add(new Point(nx, ny));
				ripenedCount++;
			}
		}
	}

	day++;
}

 

---

전체 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static int M, N;
	public static int mapCount;
	public static int ripenedCount = 0; // 익은 토마토의 개수 
	public static int day = 0;
	public static ArrayList<Point> ripenedTomato = new ArrayList<>();	
	
	public static int index = 0;
    
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		M = sc.nextInt();
		N = sc.nextInt();
		mapCount = M*N; // 전체 맵 공간의 수 

		int[][] map = new int[N][M];

		for(int i = 0; i < N; i++) {
			for(int j = 0; j < M; j++) {
				map[i][j] = sc.nextInt();
				
				if(map[i][j] == 1) { // 익은 토마토 발견하면 
					ripenedTomato.add(new Point(i, j)); // 익은 토마토 리스트에 저장 
					ripenedCount++; // 익은 토마토수 +1 
				} else if(map[i][j] == -1) { // 전체 맵 공간에서 빈칸은 제외 
					mapCount--;
				}
			}
		}
		
		if(ripenedCount == mapCount) { // 처음부터 토마토가 다 익어있는 경우 
			System.out.println(0);
		} else {
			while(true) {
				int beforeSize = ripenedCount; // 익은게 있는지 확인을 위해 이전 ripenedTomato 사이즈 저장 
				
				ripen(map); // 토마토 익히기 
				
				if(ripenedCount == mapCount) { // 익힌 결과, 모든 토마토가 익은 경우 
					System.out.println(day);
					break;
				} else if(ripenedCount == beforeSize) { // 익히고 난 뒤에도 이전 사이즈와 동일하다면 모두 익지 못하는 상황 
					System.out.println(-1);
					break;
				}
			}
		}
	}

	// 토마토 익히기 
	public static void ripen(int[][] map) {
		Queue<Point> queue = new LinkedList<>();

		for(int i = index; i < ripenedTomato.size(); i++) {
			queue.add(ripenedTomato.get(i));
		}
		index = ripenedTomato.size();
		
		while(!queue.isEmpty()) {
			int x = queue.peek().x;
			int y = queue.poll().y;
		
			for(int i = 0; i < 4; i++) { // 상 하 좌 우 이동 
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx < 0 || ny < 0 || nx >= N || ny >= M) // 범위 벗어나면 pass 
					continue;
				
				if(map[nx][ny] == 0) { // 이동한 곳에 익지 않은 토마토가 있다면 
					map[nx][ny] = 1; // 익히고 익은 ripenedTomato 리스트에 추가 
					ripenedTomato.add(new Point(nx, ny));
					ripenedCount++;
				}
			}
		}
	
		day++;
	}
}

class Point {
	int x;
	int y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

 

---

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%237576/src/Main.java

KwonMinha/BOJ