[BFS] 백준 7576번 토마토 - JAVA

 

울퉁 불퉁 멋진 몸매에~

새빨간 옷을 입고~

새콤달콤 향기 풍기는~

멋쟁이 토!마!토! 토마토~

 

---

1. 문제 출처

---

 

 

 

1일 1알고리즘을 풀기위해 노력하는 나... 제법 멋져

 

 

---

2. 설계

---

 

1) 익은 토마토 4방으로 안익은 토마토가 익는다.

그렇기 때문에 익은 토마토들의 좌표를 큐에 넣고, 그 토마토들부터 4방 탐색을 시작해야겠다고 생각했다. 때문에 데이터를 입력받음과 동시에 익은 토마토(1)인 곳을 큐에 넣어줬다. 큐에 넣어주면서 이 공간의 토마토는 이미 익었다는 표시로 visited = true를 해주었다.

for(int i=0;i<h;i++) {
	for(int j=0;j<w;j++) {
		tomato[i][j]=sc.nextInt();	
		if(tomato[i][j]==1) {
			q.add(new Node(i,j,0));
			visited[i][j]=true;
		}
	}
}

 

 

2) 처음부터 다 익은 토마토의 케이스는 결과 0을 출력한다.

익을 시간이 필요없으니까 필요한 시간은 0인 것이다. 때문에 본격적인 알고리즘을 돌리기 전에 토마토가 없는 공간을 제외하고, 모두 익었는지 확인한다. 즉, visited가 모두 true인지 확인한다.

public static boolean allGrow() {
	for(int i=0;i<h;i++) {
		for(int j=0;j<w;j++) {
			if(tomato[i][j]!=-1 && visited[i][j]==false) {
				return false;
			}
		}
	}
	return true;
}

 

 

3) 토마토가 다 익은 상태가 아니라면, 익히러 가자!

미리 익은 토마토의 좌표를 넣어준 큐에서 하나씩 꺼내고, 그 좌표 기준으로 4방 탐색을 하면서 1) 경계 범위에 있는지 2) 이미 익은 토마토인지 (visited 체크) 3) 토마토가 없는 곳인지 확인해주고, 이 세 케이스에 모두 속하지 않는다면, 토마토를 익히고(visited=true), 큐에 넣는다.

 

이 과정을 큐에 익은 토마토가 다 떨어질 때까지 계속한다.

public static void grow() {
		
	int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
		
	while(!q.isEmpty()) {
		Node cur = q.poll();
		if(result<cur.day) {
			result=cur.day;
		}
		for(int d=0;d<4;d++) {
			int row = cur.r+drc[d][0];
			int col = cur.c+drc[d][1];
				
			if(row<0 || row>=h || col<0 || col>=w) continue;
			if(tomato[row][col]==-1)continue;//빈공간
			if(visited[row][col]) continue;
				
			q.add(new Node(row,col,cur.day+1));
			visited[row][col]=true;
		}
	}
}

 

 

4) 모든 토마토가 다 익었는지 확인한다.

벽에 막혀서 4방탐색이 닿지 않아 익지 않는 토마토가 생길 수 있다. 때문에 2번 과정에서 진행했던 allGrow 함수를 재사용하여 토마토가 없는 곳 제외하고, 모든 토마토가 익었는지 확인한다. (visited = true인지 확인한다.)

public static boolean allGrow() {
	for(int i=0;i<h;i++) {
		for(int j=0;j<w;j++) {
			if(tomato[i][j]!=-1 && visited[i][j]==false) {
				return false;
			}
		}
	}		
	return true;
}

 

 

---

3. 전체 코드

---

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static Queue<Node> q = new LinkedList<>();
	static boolean[][] visited;
	static int w,h,result;
	static int[][] tomato;
	static class Node{
		int r;
		int c;
		int day;
		public Node(int r, int c, int day) {
			super();
			this.r = r;
			this.c = c;
			this.day = day;
		}
		
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		w = sc.nextInt();//가로 칸의 수
		h = sc.nextInt();//세로 칸의 수
		
		//초기화
		tomato = new int[h][w];
		visited = new boolean[h][w];
		
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++) {
				tomato[i][j]=sc.nextInt();
				
				if(tomato[i][j]==1) {
					q.add(new Node(i,j,0));
					visited[i][j]=true;
				}
			}
		}
		
		//처음부터 다 익었으면 0
		if(allGrow()) {
			result = 0;
		}else {
			grow();
			//다 돌렸음에도 0인 공간이 있으면 -1
			if(!allGrow()) {
				result = -1;
			}			
		}
		
		System.out.println(result);

	}
	
	public static void grow() {
		
		int[][] drc = {{-1,0},{1,0},{0,-1},{0,1}};
		
		while(!q.isEmpty()) {
			Node cur = q.poll();
			if(result<cur.day) {
				result=cur.day;
			}
			for(int d=0;d<4;d++) {
				int row = cur.r+drc[d][0];
				int col = cur.c+drc[d][1];
				
				if(row<0 || row>=h || col<0 || col>=w) continue;
				if(tomato[row][col]==-1)continue;//빈공간
				if(visited[row][col]) continue;
				
				q.add(new Node(row,col,cur.day+1));
				visited[row][col]=true;
			}
		}
	}
	
	public static boolean allGrow() {
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++) {
				if(tomato[i][j]!=-1 && visited[i][j]==false) {
					return false;
				}
			}
		}
		
		return true;
	}

}

 

---

과거에는 BFS DFS 무서웠는데,

이제는 오히려 반가운 문제가 되었다.

햅삐!