[BOJ 7576] 토마토 (G5)

📍 문제 

https://www.acmicpc.net/problem/7576

 

 

📍 문제 풀이 

 

기본적인 `bfs` 문제

시작점부터 상하좌우로 이동하며 이동점의 토마토가 익었는지 확인한다

익지않은 토마토가 존재한다면

1. 익은 토마토로 변경
2. 토마토의 위치를 큐에 저장
3. 큐에 저장시 `day+1`로 저장

큐가 빌때까지 위의 과정을 반복한다.

큐가 비었을 때, 토마토가 모두 익었다면 해당 최종적인 `day`를 출력

모두 익지 않았다면 `-1`을 출력

 

일차원 배열을 사용해도 되지만, 생성자를 이용하는 것을 선호하기 때문에

토마토 위치의 `x`,`y`값과 날짜를 저장해주는 생성자를 만들었다.

아래와 같이 생성자를 만들면 큐에 저장하는 시점에 `day+1`을 넘겨주면 된다

class Tomato{
	int x;
	int y;
	int day;

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

 

📍 전체 코드

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

class Tomato{
	int x;
	int y;
	int day;

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

public class boj_7576 {
	static int m,n;
	static int[][] tomatos;
	static int[] dx = {0, 0, -1, 1};
	static int[] dy = {1, -1, 0, 0};
	static Queue<Tomato> que = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		m = Integer.parseInt(st.nextToken());
		n = Integer.parseInt(st.nextToken());
		tomatos = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				// 1: 익은 토마토
				// 0: 익지않은 토마토
				// -1: 토마토가 들어있지않은 칸
				tomatos[i][j] = Integer.parseInt(st.nextToken());
				if (tomatos[i][j] == 1) {
					// 익은 토마토의 위치 큐에 저장
					que.add(new Tomato(i, j, 0));
				}
			}
		}

		bfs();

	}

	public static void bfs() {
		int day = 0;

		while(!que.isEmpty()) {
			Tomato cur = que.poll();
			day = cur.day;

			for (int i = 0; i < 4; i++) {
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if(nx < 0 || nx >= n || ny < 0 || ny>= m) continue;

				if (tomatos[nx][ny] == 0) {
					tomatos[nx][ny] = 1;	// 익지 않은 토마토라면 익은 상태로 변경
					que.add(new Tomato(nx, ny, day + 1));	// 익은 상태니깐 큐에 삽입
				}
			}
		}

		if (chkTomato()) {
			System.out.println(day);
		} else {
			System.out.println(-1);
		}
	}

	// 익지 않은 토마토가 있는지 확인
	public static boolean chkTomato(){
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(tomatos[i][j] == 0) return false;
			}
		}
		return true;
	}
}