[BOJ] 7576. 토마토 (Java)

며칠 전 BFS 알고리즘 계의 바이블이라고 불리는 토마토 문제를 처음으로 풀어보았다.

링크: https://ming-jee.tistory.com/3

연습 - [BOJ] 7576. 토마토

 

근데 처음 풀어보는 유형의 BFS라서 (큐를 2개 이용해야하는 것) 다른 사람들의 코드를 참고한 부분이 많았다.

물론, 처음부터 끝까지 다 곱씹어가며 이해하면서 작성하긴 했지만!

 

그래서 시간이 좀 지난 후에 내가 온전히 스스로 문제를 풀어보기로 했다.

예상치 못한 몇 군데 부분에서 약간 지지고 볶기는 했지만 결론적으로 잘 마무리 되기는 했는데 지난 토마토 연습 글에서 미처 몰랐던, 혹은 잘못 알았던 부분에 대해서 추가적으로 몇 자 적어보려고 한다.

 

 

▼아래 더보기를 누르면 코드 전체를 볼 수 있습니다.

[코드 보기]

	import java.io.BufferedReader;
	import java.io.IOException;
	import java.io.InputStreamReader;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.StringTokenizer;
	/* @date: 2020/03/30
	* @author: psS2mj
	* @brief: BOJ_7576_토마토 */
	public class Main_7576_토마토 {
	static int N, M, firstCheck=0, dayCnt=-1;
	static int[][] tomato;
	static int[][] visited;
	static Queue<int[]> que = new LinkedList<int[]>();
	static Queue<int[]> tq = new LinkedList<int[]>();
	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()); // 세로
	tomato = new int[N][M];
	visited = new int[N][M];
	for (int i = 0; i < N; i++) {
	StringTokenizer st2 = new StringTokenizer(br.readLine());
	for (int j = 0; j < M; j++) {
	tomato[i][j] = Integer.parseInt(st2.nextToken());
	if(tomato[i][j]==0) {firstCheck++;}
	}
	}
	// 만약 저장될 때부터 모든 토마토가 익어있는 상태라면 종료 (익지 않은 토마토가 하나도 없을 때)
	if(firstCheck==0) {
	System.out.println("0");
	return;
	}
	// 그 외
	bfs();
	// 만약 토마토가 모두 익지는 못하는 상황이라면 종료 (bfs 후 토마토 배열에 익지 않은 토마토가 있을 때)
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if(tomato[i][j]==0) {
	System.out.println("-1");
	return;
	}
	}
	}
	System.out.println(dayCnt);
	}
	// 상하좌우
	static int[] dy = {-1,1,0,0};
	static int[] dx = {0,0,-1,1};
	private static void bfs() {
	// 맨 처음부터 익어있는 토마토들의 좌표를 큐에 넣는다.
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	if(tomato[i][j]==1) {
	visited[i][j] = 1; // 뺄 수도 있긴 하지만 방문표시라는 목적에 부합하게 1로 초기화
	tq.offer(new int[] {i,j});
	}
	}
	}
	// 그 다음날부터는 이곳에서 반복적으로 처리
	while(!tq.isEmpty()) {
	int size = tq.size();
	for (int i = 0; i < size; i++) {
	que.offer(tq.poll());
	}
	while(!que.isEmpty()) {
	int[] curr = que.poll();
	int cy = curr[0];
	int cx = curr[1];
	for (int d = 0; d < 4; d++) {
	int ny = cy + dy[d];
	int nx = cx + dx[d];
	if(!check(ny,nx)) {continue;}
	if(tomato[ny][nx]==0 && visited[ny][nx]==0) {
	visited[ny][nx] = visited[cy][cx] + 1;
	tomato[ny][nx] = 1;
	tq.offer(new int[] {ny,nx});
	}
	}
	}
	dayCnt++;
	}
	}
	private static boolean check(int ny, int nx) {
	if(ny<0 || nx<0 || ny>=N || nx>=M) {return false;}
	return true;
	}
	}

view raw Main_7576_토마토.java hosted with ❤ by GitHub

 

 

생각, 생각, 생각을 해보자!

<깨달은 내용>

1. 큐의 사이즈를 for문의 조건으로 넣으면 위험한 이유

int size = tq.size();
for (int i = 0; i < size; i++) {
	que.offer(tq.poll());
}

연습 코드에서 뭔가 더 발전시켜 보고자 (코드를 줄여보고자?) 처음에는 for문의 i < size 대신 i < tq.size() 구문을 넣었다.

나는 아예 bfs를 돌릴 때 토마토가 다 익는 최소날짜를 구하기 위해 dayCnt라는 변수를 1씩 증가시켜줬는데 이게 연습 때와 달리 계속 비정상적인 숫자가 나오는 거다. (※참고: tq는 큐다.)

아무래도 이상해서 디버깅을 해보니 놀랍게도 tq에 들어있는 좌표의 개수보다 for문을 적게 돌고 있었다.

 

좀 더 자세히 살펴보니 

for (int i = 0; i < tq.size(); i++) {
	que.offer(tq.poll());
}

여기서 조건 자체를 tq.size()로 해버리면 tq에서 poll을 한 번 하고 다시 for문의 조건문으로 돌아오는 순간 맨 처음에 생각했던 반복횟수보다 1이 줄어든다. 그리고 for문을 돌 때마다 그게 반복된다.

 

그래서 처음에 size 변수에 아예 tq.size() 값을 넣고 시작하는거구나.

직접 얻어 맞으면서 배우기 꿀잼🐻🍯

 

 

2. 지난 연습 포스팅 글에서는 마지막에 dayCnt가 1 더 증가하는 이유를 '마지막에 tq에 원소가 하나도 없어서 빠져나올 때도 1이 더해짐.' (출처: https://ming-jee.tistory.com/3)라고 적었는데 그게 아니었던 것 같다.

 

tq에 원소가 하나도 없어서, 즉, 비어있어서 while문을 벗어날 때는 dayCnt 변수와 상관이 없다.

그럼에도 불구하고 마지막에 dayCnt의 값이 또 한 번 1 증가되는 이유는 내가 bfs가 끝났다고 생각했던 시점에 아직 que에 남아있는 좌표가 있기 때문에 (조건문에 의해 100% 걸러질 애들이지만) 어쨌든 tq가 비어있지 않아서 한 번은 더 돌게 된다. 거기까지 돌아야 이제 더 이상 tq에 삽입되는 원소가 없어져서 비어지는 것이므로. 그러니까 더이상 퍼질 데가 없어서 그 전날의 날짜로 결과값이 끝나야 하는데 이 과정을 거침으로써 (dayCnt 변수 입장에서는) 쓸데없이 1일이 더 추가된다고 말하면 좀 이해가 쉬우려나...🤔

 

결론은 tq에 원소가 더 이상 없어서 while문을 빠져나올 때 마지막으로 dayCnt의 값이 증가하는 것이 아니라,

bfs가 끝나기 전에 마지막으로 돌면서 dayCnt도 마지막으로 한 번 더 값이 증가하는 것이었다.

 

(이건 내 코드이고 내 생각이어서 나만 이해하는 말일듯ㅎㅎ😋)

 

 

 

- 아무튼, 끝 -