백준 7576번: 토마토 [BFS] -Java

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

7576번: 토마토

익은토마토 안익은토마토 토마토토마토

 

<Java 코드>

package algorithm.boj;

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


public class Boj7576 {
	
	public static int map[][];
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		System.setIn(new FileInputStream("Test.txt"));
		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());

		map = new int[N][M];
		boolean visit[][] = new boolean[N][M];
		int zero = 0;

		Queue<Pos> q = new LinkedList<Pos>();

		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.add(new Pos(i, j, 0));
					visit[i][j] = true;
				} else if (map[i][j]==0){
					zero++;
				}
			}
		}

//		if (checkTMT(N,M)) { // 모든 토마토가 다 익어있는지?
		if(zero==0) {
			System.out.println(0);
			return;
		}

		int dx[] = { 0, 1, 0, -1 };
		int dy[] = { 1, 0, -1, 0 };

		while (!q.isEmpty()) {
			Pos pos = q.poll();
			
//			print(N,M);


			// 4방향 토마토 익히기
			for (int i = 0; i < 4; i++) {
				int nx = pos.x + dx[i];
				int ny = pos.y + dy[i];

				// 범위체크
				if (nx < 0 || nx >= N || ny < 0 || ny >= M)
					continue;

				// 방문여부 체크
				if (visit[nx][ny])
					continue;
				
				if (map[nx][ny]==-1)
					continue;
				
				q.add(new Pos(nx,ny,pos.time+1));
				map[nx][ny]=1;
				zero--;
				visit[nx][ny] = true;
				
//				if (checkTMT(N,M)) {
//					System.out.println(pos.time+1);
//					return;
//				}
				// 다 익었는지 전체 체크
				if(zero==0) {
					System.out.println(pos.time+1);
					return;
				}
			}

		}
		
		System.out.println(-1);
		

	}

	public static void print(int N, int M) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(map[i][j]+"\t");
			}
			System.out.println();
			
		}
		System.out.println("===========================================");

	}
	
	public static boolean checkTMT(int N, int M) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if(map[i][j]==0 )
					return false;
			}
		}
		return true;
	}

	static class Pos {
		int x;
		int y;
		int time;

		public Pos(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}