Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

24. DFS와 BFS

그래프를 순회하는 알고리즘을 배워 봅시다.

Java / Python

6. 토마토

7576번

BFS로 토마토를 익히는 문제

이번 문제는 토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하는 문제입니다. (단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다.)
BFS 탐색을 이용했습니다.

• Java

import java.io.*;
import java.util.*;

class tomato{
	int x;	// 세로
	int y;	// 가로
    
	tomato(int x, int y){
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int N, M;
	static int[][] board;
	static int result = 0;
	static Queue<tomato> queue;	
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		M = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());	
        
		board = new int[N][M];     
		queue = new LinkedList<tomato>();  
        
		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)
					queue.add(new tomato(i,j));
			}
		}
		bfs();
		bw.write(result + "\n");
        
		bw.flush();
		bw.close();
		br.close();
	}
	public static void bfs(){
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 1)
					//익은 토마토가 있는 모든 위치를 큐에 담는다.
					queue.add(new tomato(i, j));
			}
		}		
		while(!queue.isEmpty()) {		
			tomato tom = queue.poll();
            
			for(int i = 0; i < 4; i++) {
				int nx = tom.x + dx[i];
				int ny = tom.y + dy[i];
                
				if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
					if(board[nx][ny] == 0){
						queue.add(new tomato(nx, ny));						
						board[nx][ny] = board[tom.x][tom.y] + 1;                       
					}
				}
			}
		}
		result = 0;
        
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(board[i][j] == 0){
					result = -1;
					return;
				} 
				result = Math.max(result, board[i][j]);
			}
		}
		result = result - 1;  
	}
}

• Python

from collections import deque
import sys
M, N = map(int, sys.stdin.readline().split())
tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

# queue 방식 사용 (deque 필수 X)
queue = deque() 

for i in range(N):
    for j in range(M):
        if tomato[i][j] == 1:
            queue.append([i, j])
            
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# bfs 경로 탐색
while queue:
    x, y = queue.popleft()
    
    for k in range(4):
        nx = x + dy[k]
        ny = y + dx[k]
        
        if 0 <= nx < N and 0 <= ny < M and tomato[nx][ny] == 0:
            tomato[nx][ny] = tomato[x][y] + 1
            queue.append([nx, ny])

result = -2
check = False # 안 익은게 있는지 확인

for i in tomato:
    for j in i:
        if(j == 0):
            check = True
        result = max(result, j)
        
if check:
    print(-1)
elif result == -1:
    print(0)
else:
    print(result - 1)