[ 백준 C++ ] 7576번 토마토 (BFS)

문제 

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

7576번: 토마토

 

코드 다 만들었는데 제출 누르고 날아가서 의욕을 잃었다. 따라서 이번엔 코드가 없다. 

 

며칠이 지나야 토마토가 다 익는지 구하는 문제

익은 토마토와 인접한 토마토는 하루가 지나면 익는다.
(인접 : 상하좌우)

2 <= M 가로 N 세로 <= 1000

1 : 익은토마토 , 0: 익지않은 토마토 , -1 빈칸 

1) 익은 토마토를 찾는다. 
2) 익은 토마토의 주변 토마토를 큐에 넣는다. 
3) 다음 반복 때 DAY +1 해준다. 
4) 다 돌았는데 익을 수 있는 토마토 없으면 -1 출력 

처음엔 이렇게 생각했었는데 예시를 보다보니 익은 토마토가 한개만 있는 것이 아니었다. 그래서 DAY를 어떻게 셀 수 있을까 하다가 아래의 방법을 사용했다. ( 문제를 충분히 보고 생각을 하자 )

 

처음 탐색할때 1인 곳의 위치를 vector<make_pair<int, int>> v 에 넣었다가 bfs에서 큐에 넣어줬다. ( 바로 큐에 넣었어도 괜찮았을것같다. )

 

주변에 있는 익지않은 토마토 map[a][b] = 0 을 이전에 있던 값 +1 해줬다. 

6 4
1 -1 0 0 0 0
0 -1 0 0 0 0
0 0 0 0 -1 0
0 0 0 0 -1 1

이 예시를 보면 

1 -1 0 0 0 0

2 -1 0 0 0  3 

3 0 0 0 -1  2 

0 0 0 0  -1 1

이런식으로 만들었다. 

 

bfs() 를 돌고 나서 맵을 다시 이중 for 문을 돌면서 확인 한다. 

그 때 0이 있으면  -1 을 출력한다. ( 모든 토마토가 익지 않았기때문) 

day(변수)보다 더 큰 값이 들어있으면 day 값을 그 값으로 바꿔준다. 

day-1 출력하면 끗 -!