백준 7576 토마토

• 입력 : 세로 크기 N, 가로 크기 M ( 2 <= M,N <= 1,000 )

        1 = 익은 토마토, 0 = 익지 않은 토마토, -1 = 토마토가 들어있지 않은 칸

• 출력 : 토마토가 모두 익을 때까지의 최소 날짜 출력, 저장될 때부터 모든 토마토가 익었다면 0,                              모두 익지 못하는 상황이면 -1 출력

---

• 문제 해결 :  

1) 입력을 받으면서 익은토마토의 위치를 큐에 PUSH하고 (BFS를사용), 안 익은 토마토의 갯수를 저장한다.

1-1) 안익은 토마토가 없다면 모두 익은것이므로 0을 출력하고 끝낸다.

1-2) 아니라면 큐를 이용하여 BFS를 시작한다.

2) day를 기록하기위해 큐에 들어간 사이즈만큼 탐색을 해야한다.

3) BFS의 조건 ( 토마토가 들어있지않은곳, 맵 밖 벗어난곳 ) 을 생각하여 큐에 넣는다

4) 큐 사이즈만큼 POP이 끝났으면 하루가 지난것이므로 day를 증가

5) 큐가 비어있을때까지 반복한다.

< 작성 코드 >

#include <iostream> #include <queue> using namespace std; typedef struct coordinate { int x; int y; }; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int m, n; // 가로m 세로n int map[1000][1000]; int visit[1000][1000]; int tomato_count; queue<coordinate> qu; int day = -1; void input() { cin >> m >>n; for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) { cin >> map[i][j]; if (map[i][j] == 1) qu.push({ i,j }); // 익은 토마토의 자리는 큐에 넣어준다. else if (map[i][j] == 0) tomato_count++; // 안익은 토마토의 갯수를 카운트한다. } } void bfs() { // tomato_count 가 모두 소진됐다면 토마토가 모두 익은것 // tomato_count 가 남아있다면 ( 0 이상 ) 토마토가 익지 못하는 상황 -> -1 출력 while (!qu.empty()) // 큐가 공백이 될때까지 반복한다 { int queue_size = qu.size(); // 큐 사이즈 변수.. 큐 사이즈만큼 pop을 돌리고 day를 카운트 for (int i = 0; i < queue_size; i++) { coordinate temp = qu.front(); // 큐의 최하단 원소 빼내어 변수에 저장 qu.pop(); // 이미 bfs를 통해 방문했던 곳이라면 패스, 아니면 visit 배열에 체크 if (visit[temp.x][temp.y]) continue; else visit[temp.x][temp.y] = 1; // 맵 경계선, 토마토가 들어있지않은곳 검사하여 사방좌표를 큐에 넣어준다. for (int j = 0; j < 4; j++) { int x = temp.x + dx[j]; int y = temp.y + dy[j]; if (x < 0 || x >= n || y < 0 || y >= m) continue; else if (map[x][y] == -1) continue; else if (map[x][y] == 0) { qu.push({ x,y }); map[x][y] = 1; tomato_count--; } } } // 큐 사이즈만큼 돌렸으면 day 하나 증가시킨다. day++; } // 안익은 토마토가 남아있다면,, if (tomato_count > 0) day = -1; } int main() { input(); // 안익은 토마토가 없다면 모두 익은것이므로 0 출력 if (tomato_count == 0) day = 0; else bfs(); cout << day; return 0; }