[c++] 백준 토마토(7576), BFS, 반례모음

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

• 격자 모양에 안익은 토마토와 익은 토마토가 존재
• 익은 토마토는 하루가 지날 때마다 인접한 안익은 토마토를 익게 만듬
• 모든 토마토를 익게 만드는데 걸리는 날짜는?

 

반례모음

2 2 1 1 1 1 0

5 3 0 -1 0 0 0 -1 -1 0 1 1 0 0 0 1 1 -1

2 2 -1 0 0 1 1

3 3 1 0 0 0 0 -1 0 -1 0 -1

3 3 0 0 1 0 0 1 0 0 1 2

3 3 -1 0 -1 0 1 0 -1 0 0 2

 

풀이

• 익은 토마토들 각각으로부터 BFS를 수행해 인접한 토마토를 익게 만든다.
• 마치 멀티 프로세스처럼 하루마다 동시에 수행하는 것처럼 보임
• 그러나, 이는 현재 익은 토마토의 위치 정보들을 큐에 쌓아서 순차적으로 인접한 토마토를 익게 만들면 된다.
• 여기서, 최소 일수는 최단 거리와 동일하다. 즉, 현재까지 이동한 거리만큼 계속 더해주면 된다. 
• 큐가 비었을 때, 토마토가 모두 익었으면 최소 일수를 출력, 나머지 조건처리 해주면 됨.

 

코드

 

• 벡터로 맵을 생성
• 반복문으로 토마토 정보를 입력 받음
• 안익은 토마토는 count
  추후에 익혀진 토마토의 개수와 일치하면 모두 익은 것임.
• 익은 토마토 좌표는 큐에 쌓아준다. 

 

 

 

 

 

 

 

 

 

 

• BFS를 이용하여 map에 대한 정보를 업데이트 하는데, 익은 토마토의 인접한 좌표들에서 안익은 토마토가 익었을 때 이동 거리만큼 map을 업데이트 해준다. 그리고 그때마다 max_day라는 변수에 최소 일수를 갱신. 
• 안익은 토마토 -> 익은 토마토 바뀔 때마다 tomato_change_count를 증가시켜줌.
• 가능한 모든 안익은 토마토를 변경이 끝나면, 간단히 조건문으로 처리한다.

 

알게 된 점

• BFS를 더 잘 다룰 수 있게 되었음.
• 큐에 대한 이해를 기반으로 잘 해결함. 

 

git 코드

https://github.com/intlabSeJun/c-plus-coding-test/blob/master/9.%20BFS/%ED%86%A0%EB%A7%88%ED%86%A0(7576).cpp