KOMAS

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

• 문제 이해
• 해결 방법
• 구현 코드

문제 이해

기본적으로 BFS를 이용한 위, 아래, 좌, 우를 0이면 1로 바꾸는 Flood fill 문제인 것은 알 수 있었다.

이 문제는 BFS의 기본 문제들과는 다르게 Flood fill의 시작 위치가 여러 개인 점이 기본 문제와는 달랐다.

Queue의 특성상 시작 토마토의 위치들인 1인 지점들을 bfs 함수를 실행 하기 이전에 전부 미리 넣어준 후

bfs를 하면 될 것 같다는 점은 쉽게 파악할 수 있었다.

그 이후 bfs를 이용해 기존하던 방식으로 각 상자에서 토마토가 1이므로 1의 주변을 익어가게끔 하면 되는 문제였다.

-1인 벽을 처리해주어야 하는 요구사항이 있지만 어차피 bfs를 할 때 0인 조건만 1로 만들어주면 되므로 0일 때만

새로운 토마토 객체를 생성해주면 되었다.

해결 방법

bfs를 실행하기 이전에 시작 토마토들인 1의 위치를 전부 Queue에 넣어 주어주어야 했다.

넣어주는 과정은 입력을 받는 과정에서 1이라면 Queue에 행, 열 위치를 알 수 있는 토마토 객체를 생성하여 넣어주었다.

추가로 토마토 객체를 생성할 때 인스턴스 변수로 며칠이 지났는지 확인할 수 있는 day를 만들어 주었다.

새로운 객체를 생성할 때 현재 Queue에서 꺼낸 반복문을 돌아가는 객체의 day 인스턴스 변수에 +1 만 해서 새로 객체를 생성할 때 지정해준다면

새로운 토마토가 생성될 때마다 이전 토마토의 day에 +1을 하므로 최소일 수를 알 수 있다.

최소일수를 알고자 할 때 모든 객체의 day의 max를 계산하면 시간이 추가로 걸리므로 이 방법보다는 전역 변수에 day를 선언해두고

가장 마지막에 생성되는 객체의 day를 전역변수 day에 저장한다면 그것이 마지막 익는 토마토의 날짜가 될 것이다. 

bfs는 2차원 배열을 탐색할 때 자주 처리해주는 2차원 배열의 범위를 벋어 나지 않게 설정해주고, 0이면 토마토 객체를 생성하고

그 부분을 1로 바꿔주어 다시 Queue에 생성되지 않도록 하였다. 0 일 때만 처리하므로 -1 인 벽을 신경 써주지 않아도 된다.

구현 코드