[BOJ_7576] 토마토 (골드 5) - JAVA

---

🐾 알고리즘

• BFS (너비 우선 탐색) 을 활용한 재귀 알고리즘
• 델타를 이용한 4방 탐색

---

🐾 생각 포인트

• 처음에는 r,c,day를 담는 클래스를 만들지 않고, 배열을 담는 큐로 생성했었는데, 토마토가 복수개일 때 동시에 익는다는 것을 간과하여서 문제가 잘 풀리지 않았다. (동시에 익는다는 것을 코드로 나타내면, box의 값이 1일 때 queue.add해주면 된다. 1인(익은 토마토) 좌표들을 큐에 담아주고 bfs 메소드를 호출해야 하는 것이다. 
• 두번째 시도로, r, c, day를 담는 클래스를 만들었고, 그 때, 값이 1인 좌표들을 저장해주기 위해 ArrayList를 생성해주었다. (isOneList) → new tomato 주의 !!
• day를 저장해줄 변수(얘도 day) 생성하여 day를 마지막에 출력할 수 있도록 할 것.
• check 메소드를 통해 마지막 날에 안익은 토마토 (0) 이 있는지 없는지 확인한다.

 

---

🐾 소스코드

package boj;

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

class Tomato {
	int r;
	int c;
	int day;

	public Tomato(int r, int c, int day) {
		super();
		this.r = r;
		this.c = c;
		this.day = day;
	}

}

public class Main {

	static int M;
	static int N;
	static int[][] box;
	static Queue<Tomato> queue = new LinkedList<>();
	static ArrayList<Tomato> isOneList;

	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()); // 세로

		box = new int[N][M];
		isOneList = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < M; j++) {
				box[i][j] = Integer.parseInt(st.nextToken());
				if (box[i][j] == 1) {
					isOneList.add(new Tomato(i, j, 0)); //값이 1인 애들을 담아줄 리스트
				}
			}
		} // 입력끝

		bfs(M, N);
	}

	private static void bfs(int r, int c) {
		queue = new LinkedList<>();

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

		int[] dr = { -1, 1, 0, 0 };
		int[] dc = { 0, 0, -1, 1 };

		int day = 0;
		while (!queue.isEmpty()) {

			Tomato t = queue.poll();
			day = t.day;
			for (int d = 0; d < 4; d++) {
				int nr = t.r + dr[d];
				int nc = t.c + dc[d];
				if (nr >= 0 && nc >= 0 && nr < N && nc < M) {
					if (box[nr][nc] == 0) {
						box[nr][nc] = 1;
						queue.add(new Tomato(nr, nc, day + 1));
					}

				}
			}
		}

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

	}

	private static boolean check() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (box[i][j] == 0)
					return false;
			}
		}
		return true;
	}
}

---

😵‍💫 공부해야 할 점

• class 만드는 연습
• 그 class 에 담은 변수를 잘 활용할 수 있도록 연습
• cnt 하기 어려울 때는 메소드에 인자로 같이 담아주자.