백준 [자바 java] 7576번 : 토마토

처음 봤을 때에는 평소에 많이 봤던 문제인 것 같아서 쉽다고 생각했는데 시간 초과가 나서 조금 헷갈렸다.

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


class Main{
    static int n;
    static int m;
    static int[][] arr;
    static int k = 0;
    static int ok() {
    	int ok = 1;
    	for(int i = k;i<n;i++) {
    		int cnt = 0;
    		for(int j = 0;j<m;j++) {
    			if(arr[i][j] == 0) {
    				ok = 0;
    				return ok;
    			}
    			else cnt++;
    		}
    		if(cnt == m) k++;
    	}
    	return ok;
    }
    
	
 public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    m = Integer.parseInt(st.nextToken());
    n = Integer.parseInt(st.nextToken());
    arr = new int[n][m];
    Queue<Integer> queue1 = new LinkedList<>();
    Queue<Integer> queue2 = new LinkedList<>();
    int i;
    int j = 0;
    int ni = 0;
    int nj = 0;
    for(i = 0; i<n;i++) {
    	 st = new StringTokenizer(br.readLine());
    	for(j = 0;j<m;j++) {
    		arr[i][j] = Integer.parseInt(st.nextToken());
    		if(arr[i][j] == 1) {
    			queue1.add(i);
    			queue2.add(j);
    			ni = i;
                nj = j;
    		}
    	}
    }
    
    int day = 0;
   
    int now = 0;
    int a = 0;
    int b = 0;
    
    
    while(queue1.isEmpty() != true) {
    	int ii = queue1.poll();
    	int jj = queue2.poll();
    	
    	now = 0;
    	
    	if(ii == ni && jj == nj) {
    		day++;
    		now = 1;
    		
    	}
  
    			if(ii-1>=0&&arr[ii-1][jj] == 0) {
    				queue1.add(ii-1);
    				queue2.add(jj);
    				arr[ii-1][jj] = 1;
    				a = ii-1;
    				b = jj;
    			}
    			if(jj-1>=0&&arr[ii][jj-1] == 0) {
    				arr[ii][jj-1] = 1;
    				queue1.add(ii);
    				queue2.add(jj-1);
    				a = ii;
    				b = jj-1;
    			}
    			if(ii+1<n&&arr[ii+1][jj] == 0) {
    				arr[ii+1][jj] = 1;
    				queue1.add(ii+1);
    				queue2.add(jj);
    				a = ii+1;
    				b = jj;
    			}
    			if(jj+1<m&&arr[ii][jj+1] == 0) {
    				arr[ii][jj+1] = 1;
    				queue1.add(ii);
    				queue2.add(jj+1);
    				a = ii;
    				b = jj+1;
    	        }
    			
    if(now ==1) {
    	
            ni = a;
    		nj = b;
    }
    }
    
    if(ok() == 1) System.out.println(day-1);
    else System.out.println(-1);
 }

 }

처음에는 계속 돌면서 채워져 있는 칸을 기준으로 위 아래 양옆을 칠해주는 방식으로 해서 시간 초과가 났다. 그래서 생각해낸 방법이 bfs를 이용하는 방식이다. 칠해져 있는 곳을 찾으면 위아래 양 옆 중 비어있는 곳을 큐에 넣는다. 그리고 한 day의 끝인 위치를 저장해서 나오면 day에 1을 더해주는 방식이다. 

 

알아야 할 점

시간을 줄여야 할 때에는 dfs를 해야한다.

 

다른 사람 코드와 다른 점 : 

1. if문을 네 개로 쓰지 않고 {0,1,0,-1} {1,0,-1,0} 이런 식으로 했다.

2. 스택에 넣을 때 전달해준 배열의 값에 1을 더해서 넣어준다 -> max값을 구한다.