[BOJ] 7576. 토마토 (Java)

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

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

연습 - [BOJ] 7576. 토마토

 

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

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

 

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

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

 

 

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

[코드 보기]

 

 

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

<깨달은 내용>

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도 마지막으로 한 번 더 값이 증가하는 것이었다.

 

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

 

 

 

- 아무튼, 끝 -