[BOJ 7576번] 토마토(JAVA)

www.acmicpc.net/problem/7576

7576번: 토마토

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

class Dot{
	int x, y;
	Dot(int x, int y){
		this.x=x;
		this.y=y;
	}
}

class Main{
	
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static int N, M, cnt=0, sum=0, goal=0;
	static int[][] map;
	static boolean[][] isVisit;
	static int[] dx= {0, 1, 0, -1};
	static int[] dy= {1, 0, -1, 0};
	
	public static void main(String args[]) throws Exception {
		String s[]=br.readLine().split(" ");
		M=Integer.parseInt(s[0]);
		N=Integer.parseInt(s[1]);
		map=new int[N][M];
		isVisit=new boolean[N][M];
		for(int i=0;i<N;i++) {
			String s1[]=br.readLine().split(" ");
			for(int j=0;j<M;j++) {
				map[i][j]=Integer.parseInt(s1[j]);
			}
		}
		bfs();
	}
	
	public static void bfs() {
		Queue<Dot> q=new LinkedList<>();
//		토마토가 익었으면 큐에 삽입
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]==1) q.add(new Dot(i, j));
			}
		}
		
		while(!q.isEmpty()) {
			Dot dot=q.poll();
			for(int i=0;i<4;i++) {
				int nextX=dot.x+dx[i];
				int nextY=dot.y+dy[i];
//				범위를 벗어난 경우 패스
				if(nextX<0||nextY<0||nextX>=N||nextY>=M) continue;
//				익지 않은 토마토가 아니면 패스,
				if(map[nextX][nextY]!=0) continue;
//				현재 위치=전 위치 +1(일수를 계산)
				map[nextX][nextY]=map[dot.x][dot.y]+1;
				q.add(new Dot(nextX, nextY));
			}
		}
		int max=0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(map[i][j]==0) {
					System.out.println(-1);
					return;
				}
				max=Math.max(max, map[i][j]);
			}
		}
		System.out.println(max-1);
	}
}

BFS를 이용해서 탐색을 해보았습니다.

Dot이라는 클래스를 만들어 x좌표와 y좌표에 대한 정보를 담았고, Dot 객체를 담는 큐를 만들어 이를 이용해 BFS 탐색을 시도해보았습니다.

map이라는 이중배열에 토마토의 0 -1 1여부를 저장했고, 추후에 이 이중배열에 일수를 저장했는데요, 최종적으로 map의 최댓값에서 -1을 한 값이 토마토가 모두 익는 데 걸리는 시간이 되었습니다.

그리고 최종적으로 탐색을 마쳤는데도 0이 남아있다면 -1을 출력하도록 했습니다.

 

아직 BFS 탐색이 익숙치 않아 아래 블로그 링크를 참고하며 풀었습니다.

zoonvivor.tistory.com/131

[BOJ] 백준 7576 - 토마토 (자바)