[알고리즘] 백준7576 토마토 - 자바

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

7576번: 토마토

 

 

[풀이 코드]

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

public class BOJ_7576_토마토 {
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static int M; // 가로
	static int N; // 세로
	static int[][] graph;
	static Queue<int[]> q = new LinkedList<>();;
	
	static void bfs() {
		
		while(!q.isEmpty()) {
			int y = q.peek()[0];
			int x = q.peek()[1];
			q.poll();
			
			for(int l=0; l<4; l++) {
				int yy = y + dy[l];
				int xx = x + dx[l];
				if(yy >= 0 && yy < N && xx >= 0 && xx <M) {
					if(graph[yy][xx] == 0) {
						graph[yy][xx] = graph[y][x] + 1;
						q.offer(new int[] {yy, xx});
					}
				}
			}
			
		}
	}
	
	public static void main(String[] args) throws IOException {
		// 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());
		
		graph = new int[N][M];

		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				graph[i][j] = Integer.parseInt(st.nextToken());
			}
		}//for문 종료
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(graph[i][j] == 1) {
					q.offer(new int[] {i, j});
				}
			}
		}//for문 종료
		
		bfs(); //탐색
		
		int max = 0;
		boolean flag = false; // 0 찾기
		for(int i=0; i<N; i++) {
			for(int j=0; j<M; j++) {
				if(graph[i][j] == 0) {
					flag = true; // 0이 하나라도 있다면
				}else {
					max = Math.max(max, graph[i][j]-1);
				}
			}
		}
		if(flag) {
			System.out.println(-1);
		}else {
			if(max > 0) {
				System.out.println(max);
			}else {
				System.out.println(0);
			}
		}
		
	}

}

• 이 문제는 출력 조건이 은근히 까다로웠다. 어찌어찌 답은 나왔는데 효율적인 건 잘 모르겠다.
  
  
• 이 문제에서 중요하다고 생각되는 건 먼저 큐에 담을 토마토를 찾는 것이다. 예제 입력 중에 익은 토마토가 양 끝단에 있는 경우가 있는데 큐에 하나만 넣고 탐색을 한다면 당연히 오답이 나온다. 먼저, 익은 토마토를 찾고 그 즉시 큐에 넣는 것이 핵심이었다.
  
  
• vistied배열은 필요 없었다. 늘 필요할 것 같아서 무의식적으로 만들었지만 이미 graph에 갱신을 해주면서 탐색을 해서 굳이 선언할 필요가 없었다.