BOJ - 7576 ) 토마토

 

 

---

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

7576번: 토마토

 

---

익은토마토가 주변에 안익은 토마토를 전파하면서 퍼지는 문제이다.

 

퍼질때에 값이 일정하게 ( 시간이 + 1 ) 씩 증가하므로 

 

BFS로 퍼지는 최대시간을 구해준다.

 

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception{
		int dir[][] = {{1,0},{-1,0},{0,1},{0,-1}};
		int answer =0;
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		int n = Integer.parseInt(st.nextToken());
		int map[][] = new int[n][m];
		ArrayDeque<int []> dq = new ArrayDeque<>();
		//  0 번째는 y 좌표 1번째는 x 좌표 2번째는 날짜
		for (int y = 0 ; y<n ;y++) {
			st = new StringTokenizer(br.readLine());
			for(int x= 0 ; x < m ; x++) {
				map[y][x] = Integer.parseInt(st.nextToken());
				if(map[y][x]==1) dq.add(new int[] {y,x,0});		
				// 1이면 시작점이기 때문에 큐에 넣어준다.
			}
		}
		while(!dq.isEmpty()) {
			int now[] = dq.poll();
			int now_y =now[0]; int now_x = now[1]; int time = now[2];
			answer = time;
			for(int index = 0 ; index < 4 ; index++) {
				int next_y = now_y + dir[index][0];
				int next_x = now_x + dir[index][1];
				if(next_y >=0 && next_x >= 0 && next_y < n && next_x <m) {
					if(map[next_y][next_x]==0) {
						// 다음 장소가 익지않은 토마토라면, 1로 변경한후에 시간을 늘리고 큐에 넣어준다.
						map[next_y][next_x]=1;
						dq.add(new int[] {next_y , next_x , time+1});
					}
				}
			}
		}
		
		for(int y = 0 ; y < n ; y++) {
			for(int x = 0 ; x < m ; x++) {
				// BFS가 끝나고 익지않은 토마토가 있다면, -1을 출력한다.
				if(map[y][x]==0) answer = -1;
			}
		}
		System.out.println( answer );
	}
	
}

---

확실하게 C++ 이 메모리나 시간이나 좀 더 좋은것같다.