[JAVA]백준_7576_토마토

문제링크

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

7576번: 토마토

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 Main{
	
	static int N,M;
	static int map[][];
	static Queue<Node> q = new LinkedList<>();
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	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());
		
		map = new int[N][M];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				if(map[i][j] == 1) q.offer(new Node(i,j));
				
			}
		}
		
		bfs();
		
		int max = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j] == 0) {
					System.out.println(-1);
					return;
				}
				max = Math.max(max, map[i][j]);
			}
		}
		
		System.out.println(max-1);
	}
	
	static void bfs() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=M) continue;
				if(map[nx][ny]!=0) continue; //막힌길이거나 이미 익었으면 안감
				
				map[nx][ny] = map[node.x][node.y]+1; //현재 토마토 +1만큼 늘어가니까 최대 시간 구할 수 있다.
				q.add(new Node(nx,ny));
			}
		}
	}
	
	static class Node{
		int x;
		int y;
		public Node(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
	}
}

 

토마토 익는 시간을 구하는 것이 관건인 듯?하다

그리고 이전에 bfs문제를 풀 때는 처음 시작할 때 초기값만 큐에 넣어서 시작했으면 토마토는 현재 토마토를 모두 다 넣어서 구해야한다.

그래서 초반에는 현재 토마토를 따로 ArrayList에 저장하고 이 ArrayList를 저장하는 큐를 만들어서 풀었으나

굳이 이렇게 복잡하게 풀 필요가 없었으며 이렇게 풀면 시간초과가 난다!!

그냥 초반에 토마토의 위치를 큐에 넣고 똑같이 bfs로 풀면된다.

토마토를 익는 시간을 구하는 것은 현재 토마토에서 옆으로 뻗어나갈 수록 현재 토마토의 위치 map[i][j]+1 을 해주면된다.

초기에는 토마토가 1이었으면 익으면 주변은 2

2가 익으면 주변은 3

...

이렇게 이어진다. 따라서 제일 max인 값이 다 익을 때 까지 걸리는 시간이라고 생각하면된다.

또한 isVisited배열이 따로 필요가없다. 갔는지 안갔는지 굳이 체크할 필요 없이 익었으면 뛰어넘으면?되니까