[백준] 7576번 토마토 (BFS_JAVA)

BFS 문제!

 

일반적인 BFS문제에서,

조금만 변형하면 시간이 많이 단축된다.

 

---

문제

 

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

7576번: 토마토

 

 

---

설계

 

알고리즘 설계 [접근 방법] : BFS

2차원 배열을 탐색하면서, 가장 빠른 길을 찾는 방법인 BFS로 풀었다.

특별할 건 없고, 평범한 BFS 문제다!

 

 

풀이 과정

1.

2차원 배열의 크기인 w와 h를 입력받는다.

그리고 2차원 배열인 map을 생성하고, 토마토 값을 입력받는다.

 

2.

BFS 메서드에 들어와서, 익은 토마토의 위치를 찾는다.

그리고 찾은 위치를 방문체크 후 queue에 넣어준다.

그리고 그 값을 1에서 -10으로 변경해준다. > 그 이유는 2차원 배열 map에 값을 토마토가 익기 위한 날짜로 값을 갱신할 예정이다. 그런데 맨 처음 입력받았을 때 1은 익었다는 표시이다. 그래서 익기 위한 날짜가 0일이지만, 1일이라고 착각할 수 있기 때문에 -10으로 값을 변경시킨다.

 

3.

사방탐색을 하며, 익은 토마토 옆에 0이 있다면 방문체크를 해주고 큐에 넣는다.

그리고 익기 위한 날짜 값인 day+1한 값을 map에 저장한다.

 

4.

queue가 비었다면, 2차원 배열인 map을 탐색하며 모든 토마토가 익을 수 있는지 확인한다.

만약 map에 0이 존재한다면, 익을 수 없는 토마토이므로 -1을 출력해야 한다.

만약 모든 토마토가 -1 또는 0보다 큰 값을 가진다면, 가장 큰 값이 모든 토마토가 익기 위한 날짜가 된다.

 

5.

answer값을 갱신하고 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_7576_토마토 {
	
	static int w, h, answer;
	static int[] r, c;
	static int[][] map;
	static boolean[][] isvisited;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		w = sc.nextInt();
		h = sc.nextInt();
		
		map = new int[h][w];
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		r = new int[]{-1, 0, 1, 0};
		c = new int[]{0, 1, 0, -1};
		isvisited = new boolean[h][w];
		
	
		answer = 0;
		BFS();
		
		System.out.println(answer);
		
	}
	
	public static void BFS() {
		Queue<int[]> queue = new LinkedList();
		
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(map[i][j]==1) {
					map[i][j]=-10;
					isvisited[i][j]=true;
					queue.add(new int[] {i, j, 0});
				}
			}
		}
		
		//사방탐색
		while(!queue.isEmpty()) {
			
			int[] curr = queue.poll();
			
			int i = curr[0];
			int j = curr[1];
			int day = curr[2];
			
			for(int k=0; k<4; k++) {
				int dr = i+r[k];
				int dc = j+c[k];
				
				if(!(0<=dr && dr<h && 0<=dc && dc<w)) continue;
				if(map[dr][dc]!=0) continue;
				if(isvisited[dr][dc]) continue;
				
				map[dr][dc]=day+1;
				isvisited[dr][dc]=true;
				queue.add(new int[] {dr, dc, day+1});
			}
		}
		
		//모든 토마토가 익을 수 있는지 계산하기
		Loop:
		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(map[i][j]==0) {
					answer=-1;
					break Loop;
				}
				
				else if(answer<map[i][j]) {
					answer=map[i][j];
				}
			}
		}
	}
}

 

 

(❁´◡`❁)

끝!