백준 7576번. 토마토 (Java)

문제 링크 : https://www.acmicpc.net/problem/7576

제 생각하는 가장 기본적인 BFS 문제입니다.

만약 누군가 BFS 개념을 이제 막 배워서 문제를 추천해달라고 한다면 이 문제를 추천할 겁니다.

<접근>

하루에 상, 하, 좌, 우 한 칸씩 이동하니 BFS가 바로 떠오릅니다.

저는 좌표 관련된 BFS 문제에서는 좌표에 대한 Class를 만들어서 사용합니다.

아래 그림처럼 배열의 숫자를 하나씩 증가시키는 방법도 있지만

저는 클래스에 변수를 하나 더 추가하여 카운트 하는 방법로 풀었습니다.

일반적으로 BFS 문제에서는 visited 2차원 배열을 사용하여 중복 방문을 방지하지만 이 문제에서는 1 이 그 역할을 하고 있습니다.

<순서>

1. 2중 for문으로 box 배열을 돌면서 익은 토마토를 Queue 자료구조에 넣기

2. bfs를 돌면서 토마토 모두 익게 하기

3. 다시 2중 for문 돌면서 안 익은 토마토가 있다면 -1 출력, 없으면 날짜 출력

	import java.util.*;
	import java.io.*;
	// https://www.acmicpc.net/problem/7576
	class Main {
	static int N;
	static int M;
	static int[][] box;
	static int[] dx = {1, -1, 0, 0};
	static int[] dy = {0, 0, 1, -1};
	static class Dot {
	int x;
	int y;
	int day;
	public Dot(int x, int y, int day) {
	this.x = x;
	this.y = y;
	this.day = day;
	}
	}
	public static void main(String[] args) throws Exception {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());
	N = Integer.parseInt(st.nextToken());
	M = Integer.parseInt(st.nextToken());
	box = new int[M][N];
	for(int i=0; i<M; i++) {
	st = new StringTokenizer(br.readLine());
	for(int j=0; j<N; j++) {
	box[i][j] = Integer.parseInt(st.nextToken());
	}
	}
	bfs();
	}
	static void bfs() {
	Queue<Dot> q = new LinkedList<Dot>();
	int day = 0;
	// 토마토가 있는 좌표 찾아서 Queue에 넣기
	for(int i=0; i<M; i++) {
	for(int j=0; j<N; j++) {
	if(box[i][j] == 1)
	q.offer(new Dot(i, j, 0));
	}
	}
	// bfs 시작
	while(!q.isEmpty()) {
	Dot dot = q.poll();
	day = dot.day;
	for(int i=0; i<4; i++) {
	int nx = dot.x + dx[i];
	int ny = dot.y + dy[i];
	if(0 <= nx && nx < M && 0 <= ny && ny < N) {
	if(box[nx][ny] == 0) {
	box[nx][ny] = 1;
	q.add(new Dot(nx, ny, day+1));
	}
	}
	}
	}
	// 토마토가 다 익었는지 확인
	if(checkTomato())
	System.out.println(day);
	else
	System.out.println(-1);
	}
	// box 배열에 0이 남아있다면 false, 아니면 true
	static boolean checkTomato() {
	for(int i=0; i<M; i++) {
	for(int j=0; j<N; j++) {
	if(box[i][j] == 0)
	return false;
	}
	}
	return true;
	}
	}

view raw BOJ7576.java hosted with ❤ by GitHub