https://www.acmicpc.net/problem/7576
문제설명
- n * m 영역에 토마토가 한 칸씩 들어간다.
- 익은 토마토는 다음날 상하좌우 토마토가 있으면 그들을 익게 만든다.
- -1로 표시 된 데는 토마토가 없는 곳이다.
- 토마토가 다 익는 데 필요한 일 수를 구하여라.
만약 기다릴 필요 없이 익어있다면, 0을 출력한다(0일의 의미)
모든 토마토가 익지 못한다면, -1을 출력한다.
아이디어
- 동시에 익어야 하므로 큐에 SEED가 되는 1인 토마토들을 동시에 넣어준다.(안 해봤는데 seed 하나씩 bfs 돌리고 나서 어떤 토마토가 익는 날을 최솟값으로 갱신해주는 것도 가능할 것 같다.)
-
자식들이 큐에 들어갈 수 있는지 검사하기:
0~n-1 / 0~m-1 영역에 있으며 아직 익지 않은 토마토 -
들어갈 수 있으면 자식의 익은날짜 = 부모+1
삽질
-
마지막에 토마토 밭 2차원 배열을 싹 돌면서 최댓값을 뽑아야했는데
int m;//최댓값 저장 변수가 토마토 밭 가로 길이 m이랑 겹쳐서^^^^^
m 이 수정돼서 전체를 못보는 경우가 생겼다. -
처음에 1인 토마토들을 동시에 넣어줄 때 외부함수를 하나 만들어서 1인 위치를 찾는 식으로 했었는데 시간초과 났다. 옛날엔 당연히 입력받으면서 큐에 넣어줬었는데 왜 그랬을까....
감상
역시 1년 전에 풀었던 문제이다. 그 땐 참 bfs dfs를 비롯해 dp까지 다 잘 풀었었는데...ㅎ.. 당시에 바로 맞았던 문젠데 다시 푸니까 3번인가 4번 틀리고서야 다른 사람 반례를 보고 풀었다.당장 1주일 뒤에 삼성전자랑 LG CNS 코테인데 어떡하지
옛날에는 visited 배열 없이도 풀었던 거 같은데 이번엔 걍 생각하기 귀찮아서 만들었다. 옛날 소스 보니까 bfs를 시작할 seed를 뽑는 과정 없이 큐에 처음에 익은 토마토들을 싹 다 넣어줬었다. 큐 상에서 날짜가 변할 때 모든 해당날짜에 익을 토마토들은 다 처리가 된다.
