[Python/파이썬, Java/자바 백준 7576] 토마토(BFS)

www.acmicpc.net/problem/7576

7576번: 토마토

 

풀이

시간초과에 주의해서

 

표를 입력받을때 1이면 바로 큐에 넣어줬습니다.

이렇게 되면 첫째날 bfs를 할 토마토만 큐 안에 있고,

 

일자별로 같은 날 들어온 토마토만 bfs 돌리기 위해서 

for문에 큐 길이만큼만 돌려주었습니다.

 

이렇게되면 첫째날 들어온 토마토만큼만 bfs 돌고 result +1

둘째날 들어온 토마토만큼만 bfs 돌고 result+1

.

.

이런식으로 탐색하여 result를 리턴시켜 출력했습니다

from collections import deque
import sys
input=sys.stdin.readline

dx=[1,-1,0,0]
dy=[0,0,1,-1]

def bfs():
    result = 0
    while q:
        result +=1
        for _ in range(len(q)):
            x,y=q.popleft()
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                if 0<=nx<n and 0<=ny<m and graph[nx][ny]==0:
                    graph[nx][ny]=1
                    q.append([nx,ny])
    return result

m,n=map(int, input().split())
graph,q=[],deque()
for i in range(n):
    row = list(map(int,input().split()))
    for j in range(m):
        if row[j]==1:
            q.append([i,j])
    graph.append(row)

result=bfs()-1
for i in range(n):
    for j in range(m):
        if graph[i][j]==0:
            print(-1)
            exit()
print(result)

 

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

public class Main{
	static int min_val=0, n , m;
	static int[][] map;
	static Queue<int[]> queue= new LinkedList<int[]>();
	static int[] dx= {1,-1,0,0};
	static int[] dy= {0,0,1,-1};

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		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) queue.offer(new int[] {i,j});
			}
		}
		
		min_val=bfs();


		boolean flag=false;
		// bfs돌고나서 익지않은 토마토가 있을지 -1 출력
		loop : for(int i=0; i<n; i++) {
			for(int j=0; j<m;j++) {
				if(map[i][j]==0) {
					System.out.println(-1);
					flag=true;
					break loop;
				}
			}
		}
		
		if(flag==false) System.out.println(min_val-1);

	}
	private static int bfs() {
		// TODO Auto-generated method stub
		int result=0;
		while(!queue.isEmpty()) {
			result+=1;
			// 일자별로 나누기 위해 같은 날에 queue에 담겨진 값들만큼 돌리기
			int tmp=queue.size();
			for(int i=0;i<tmp; i++) {				
				int[] cur=queue.poll();
				int x=cur[0];
				int y=cur[1];
				
				for(int k=0; k<4 ; k++) {
					int nx= x+dx[k];
					int ny= y+dy[k];
					if(0<=nx && nx<n && 0<=ny && ny<m) {
						if(map[nx][ny]==0) {
							map[nx][ny]=1;
							queue.offer(new int[] {nx,ny});						
						}
						
					}
				}
			}
		}
		return result;

	}
}