[BOJ] 7576번 토마토 문제풀이 (C++)

2017.12.28에 쓰여진 글 입니다.

---

 

문제링크

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

7576번: 토마토

 

풀이방법

풀이방법은 큐를 이용한 BFS 돌리기를 쓰면 된다.

BFS의 기본중의 기본 문제 랄까... 꼭 풀어보길 권하는 문제

 

소스코드

#include <iostream>
#include <queue>    //queue 위한 헤더
#include <utility>
 
using namespace std;
 
enum { BLANK = -1, TOM_X = 0, TOM_O = 1 };
//-1 빈곳, 0 안익은토마토, 1 익은 토마토 
 
int M, N;
int map[1000][1000];
queue < pair<int, int> > q;        //익은 토마토 좌표 넣는 큐
int dx[] = { -1,0,1,0 };        //방향설정
int dy[] = { 0,-1,0,1 };
int cnt;        //해당일에 현재 익어있는 토마토 갯수에서 퍼뜨릴갯수 체크하는 카운트
int day;        //정답
 
void infection(int cur_x, int cur_y)        //주변 익히는 함수
{
    for (int i = 0; i < 4; i++) {
        int new_x = cur_x + dx[i];
        int new_y = cur_y + dy[i];
        if (0 <= new_x&&new_x < N && 0 <= new_y&&new_y < M&&map[new_x][new_y] == TOM_X) { //범위안에있고 토마토가 익지 않았다면
            map[new_x][new_y] = TOM_O;                //토마토 익혀줌
            q.push(make_pair(new_x, new_y));        //익힌 그 토마토 좌표를 큐에 넣어준다
        }
    }
}
 
void solve()
{
    while (!q.empty() && cnt>0) {        //큐가 비어있지 않고, 카운트가 0보다 클때 
        int cur_x = q.front().first;    //해당좌표 넣어줌
        int cur_y = q.front().second;    //해당좌표 넣어줌
        q.pop();                        //큐 빼줌
        infection(cur_x, cur_y);        //그 해당좌표(익은토마토좌표)에서 주변하나씩 익히기 
        cnt--;                            //카운트 감소
    }
}
 
bool check()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j] == TOM_X)        //안익은 토마토가 있다면
                return false;            //false 리턴
    return true;        //모두다 익었으면 true 리턴
}
int main()
{
    cin >> M >> N;
    cnt = 0;    //카운트초기화
    day = 0;    //날짜초기화
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];                //맵입력받기
            if (map[i][j] == TOM_O) {        //만약 익은 토마토가 있다면 
                cnt++;                        //큐 카운트증가
                q.push(make_pair(i, j));    //큐에 익은토마토 좌표 넣기
            }
        }
 
    while (!q.empty()) {    //큐가 빌때까지 돌리기
        solve();            //solve 함수 호출
        cnt = q.size();        //카운트에 현재 큐 갯수 넣기
        day++;                //날짜 하루 지남
    }
    day--;        //날짜하루빼줌, 마지막 토마토에서 주변을 익힐수가없는데 그 하루가 체크될 예정이므로 
    if (!check())        //만약 안익은 토마토가 있다면 -> 토마토가 모두 익지는 못하는 상황이므로
        day = -1;        //-1 대입
    
    //정답출력
    cout << day << endl;
 
    return 0;
}