[BaekJoon] 백준 7576번 _ 토마토 for JAVA _ BFS 알고리즘

 

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

7576번: 토마토

 

 

 

 

문제

 

 

 

---

 

BFS로 풀었다.

 

 

중요한 점은... 1에서 0으로 옮겨가서 숫자를 바꾸는 식으로 짰는데

 

 

1이 여러개 있을 수 있으므로

 

 

BFS() 함수를 돌릴 때 x,y 좌표를 Queue에 넣으면 계산이 한번에 되어버린다.

 

 

뭔말이냐면

 

 

X

 

 

 

이렇게 (0, 0)에서 0(안익은) 을 쭉 훑어서 4까지 가버린다.

 

 

 

그래서 이미 map[][] 배열을 쭉 훑어서 1인 x,y 좌표를 queue에 넣어놓고

 

 

함수를 실행시켜야 한다.

 

 

 

O

 

 

 

이렇게 되어야 한다. 그리고 이 경우에 일수로 따지면 이틀이 지난 거라서 2가 출력되어야 하므로

 

제일 큰 수에서 -1 한게 출력되어야 한다.

 

 

 

또 익을 수 없는 토마토가 있을 경우에는 bfs() 함수를 모두 돌린 후에도 0이 남아있을 경우이다.

 

 

 

 

코드

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

class tomato {
	private int x, y;
	
	public tomato(int x, int y) {
		this.x = x;
		this.y = y;
	}
	
	public int getX() {
		return this.x;
	}
	
	public int getY() {
		return this.y;
	}
}

public class Baek7576 { // BFS
	public static int M, N;
	public static int map[][];
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {0, 0, 1, -1};
	public static int ans = 0;
	public static Queue<tomato> queue = new LinkedList<tomato>();
	
	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());
		
		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 tomato(i, j)); // 1일 때 queue에 넣음		
			}
		}
	
		System.out.println(tomato_bfs());
		
	}
	
	public static int tomato_bfs() {
		
		while(!queue.isEmpty()) {
			tomato t = queue.poll();
			int x = t.getX();
			int y = t.getY();
			
			for(int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx <= -1 || nx >= N || ny <= -1 || ny >= M || map[nx][ny] == -1) continue;
				
				if(map[nx][ny] == 0) {
					map[nx][ny] = map[x][y] + 1;
					queue.offer(new tomato(nx, ny));
				}
			}
		}
		
//		익을대로 익은 map[][] 확인
//		for(int i = 0; i < N; i++) {
//			System.out.println();
//			for(int j = 0; j < M; j++)
//				System.out.print(map[i][j] + " ");
//		}
		
		for(int i = 0; i < N; i++) 
			for(int j = 0; j < M; j++) {
				if(map[i][j] == 0) return -1;   // 0이 있으면 -1 출력
				ans = Math.max(ans, map[i][j]);
		}
		
		return ans - 1;
		
		
	}

}

 

 

 

 

 

 

성능

 

 

 

 

 

다른 사람의 코드를 살펴보니 효율을 올리는 방법으로 InputStream을 사용할 수 있다는걸 알게되었다.