[백준/Python] 7576번: 토마토 (JAVA버전 추가)

📖  문제 링크

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

7576번: 토마토

 

✅  최종 코드

1. Python 버전

from collections import deque
import sys
input = sys.stdin.readline
# 익은 : 1
# 익지않은 : 0
# 없음 : -1 

#세로가 n
m,n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
check = deque()
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            check.append((i, j))
            

def dfs(x, y):
    
    check.append((x, y))
    global cnt
    
    while check:
        x, y = check.popleft()         
        
        for i in range(4):
            if x<0 or x>=n or y<0 or y>=m:
                continue
            
            if board[x][y] !=0 or board[x][y] != -1:
                nx = x+dx[i]
                ny = y+dy[i]
                if nx<0 or nx>=n or ny<0 or ny>=m or board[nx][ny] != 0:
                    continue
                else: 
                    board[nx][ny] = board[x][y]+1
                    check.append((nx, ny))

 
if len(check) == (n*m):
    print(0)
    exit()
elif len(check) == 0:
    print(-1)
    exit()
else:
        
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    
    x, y = check.popleft()
    dfs(x,y)   

    for i in range(n):
        for j in range(m):
            if board[i][j] == 0:
                print(-1)
                exit()
                
    print((max(map(max, board))-1))

 

 

 

 

2. Java 버전 (2022.08.23 추가)

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

public class Main_BJ_7576_토마토 {
	
	static int M, N;
	static int[][] board;
	static boolean[][] visited;
	static int[][] res;	
	static int[] dx = {-1, 1, 0, 0};	//상, 하, 좌, 우
	static int[] dy = {0, 0, -1, 1};
	static Queue<Tomato> tomato;
	static int minTime = Integer.MIN_VALUE;
	
	static class Tomato{
		
		int x;
		int y;
		
		public Tomato(int x, int y) {

			this.x = x;
			this.y = y;
		}	
		
	}
	
	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
	
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		tomato = new LinkedList<>();
		
		board = new int[N][M];
		visited = new boolean[N][M];
		res = new int[N][M];
		int startTomato = 0;
		int all = N*M;
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<M;j++) {
				board[i][j] = Integer.parseInt(st.nextToken());
				if(board[i][j] == 1) {
					tomato.add(new Tomato(i, j));
					visited[i][j] = true;
					all -= 1;
				}
				if(board[i][j] == -1) {
					res[i][j] = -1;
					all -= 1;
				}
			}
		}
		
		startTomato = tomato.size();
		
		if(all == 0) {
			System.out.println(0);
		}	
		
		else {
			
			bfs();
			
			for(int i=0;i<N;i++) {
				for(int j=0;j<M;j++) {
					if(res[i][j] == 0) {
						startTomato -= 1;
						if(startTomato < 0) {
							System.out.println(-1);
							System.exit(0);
						}
						
					}
					else {
						minTime = Math.max(res[i][j], minTime);
					}
				}
			}
			
			System.out.println(minTime);
		}
		
		
	}//main

	private static void bfs() {
		
		
		while(!tomato.isEmpty()) {
			
			Tomato nowT = tomato.poll();
			
			int nx, ny;
			
			for(int i=0;i<4;i++) {
				
				nx = nowT.x + dx[i];
				ny = nowT.y + dy[i];
				
				if(nx >= 0 && nx < N && ny >= 0 && ny < M && !visited[nx][ny] && board[nx][ny] != -1) {
					
					if(board[nx][ny] == 0) {
						res[nx][ny] = res[nowT.x][nowT.y] + 1;
						board[nx][ny] = 1;
						visited[nx][ny] = true;
						tomato.add(new Tomato(nx, ny));
					}					
				}				
			}	
			
		}//end while				
	}// end bfs
	
	
}//end class