[백준] JAVA - 7576. 토마토

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

7576번: 토마토

생각

BFS를 사용하고 BFS가 퍼져나갈때마다 큐의 원소에 들어가는 day를 1씩 증가시켜서 걸린 시간을 나타내도록 했습니다. map의 원소를 마킹하는것보다는 이 방식이 더 나은것같습니다.

 

BFS의 시작점이 다수인경우에는 큐안에서 queue.size()만큼 반복문을 다시 돌게 해줍니다. 이렇게 하면 특정 정점으로부터 시작되는 너비 우선 탐색이 동시에 실행되게 구현할 수 있습니다.

 

Java Code

package com.java.algorithm;

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

public class BOJ_7576_토마토 {
	static int R,C;
	static int[][] map;
	static boolean[][] visited;
	static Queue<int[]> q;
	static int[] dy = {1,-1,0,0};
	static int[] dx = {0,0,-1,1};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		C = Integer.parseInt(st.nextToken());
		R = Integer.parseInt(st.nextToken());
		
		map = new int[R][C];
		visited = new boolean[R][C];
		
		q = new LinkedList<int[]>();
		
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < C; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) {
					q.add(new int[] {i, j, 0});
					visited[i][j] = true;
				}
			}
		}
		System.out.println(byBFS());
		
	}
	
	private static int byBFS() {
		int day = -1;
		//토마토 다 익었는지 체크
		boolean flag = true;
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j] == 0) {
					flag = false;
				}
			}
		}
		if(flag) return 0;
		
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0) {
				int[] now = q.poll();
				int y = now[0], x = now[1]; 
				day = now[2];
				map[y][x] = 1; // 토마토 익음
				
				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];
					if(ny >= R || ny < 0 || nx >= C || nx < 0) continue;
					if(!visited[ny][nx] && map[ny][nx] == 0) {
						visited[ny][nx] = true;
						q.add(new int[] {ny,nx,day+1});
					}
				}
				
			}
		}
		
		//토마토 다 익었는지 체크
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if(map[i][j] == 0) {
					day = -1;
				}
			}
		}
		
		return day;
	}

}