[백준 7576번] 토마토 C++

www.acmicpc.net/problem/7576

7576번: 토마토

그냥 저냥 무난했던 BFS 문제였습니다.

처음에 BFS 정말 막막했는데 확실히 풀면 풀 수록 뭔가 늘긴 하는거같네요...

 

익은 토마토가 있는 칸을, 입력받을때마다 큐에 넣어주고 visit 처리 했습니다.

토마토가 없는 칸(-1)도 입력을 받을 때 마다 visit 처리 해줬습니다

왜냐하면 나중에 visit을 전부 뜯어보며 아직 못 간곳이 있으면(visit값이 0인곳이 한 곳이라도 있으면)

토마토를 전부 익히지 못 한 케이스로 보고 -1을 출력할 것입니다.

 

bfs돌리는건 모든 1을 대상으로 한번에 스윽 돌렸습니다.

큐 사이즈를 미리 저장해서 그 만큼 반복하는게 그 예시입니다.

 

#include <iostream>
#include <queue>
 
using namespace std;
 
int m, n;
int arr[1001][1001];
bool visit[1001][1001];
 
queue<pair<int,int>> q;
 
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
//이동횟수
int cnt = 0;
 
void bfs() {
    
    while (!q.empty()) {
        int qsize = q.size();
        bool result = false;
        //큐 사이즈를 미리 저장 후 한번에 bfs해준다
        for (int i = 0; i < qsize; i++) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
 
            for (int j = 0; j < 4; j++) {
                int nx = x + dx[j];
                int ny = y + dy[j];
 
                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
                if (visit[nx][ny]) continue;
                if (arr[nx][ny] == 0) {
                    visit[nx][ny] = true;                    
                    q.push({ nx,ny });
                    result = true;
                }
            }
        }
        //만약 탐색한 곳이 아무곳도 없던 경우였다면 cnt를 올리지않는다
        if (result == true) cnt++;        
    }
}
 
int main() {
    cin >> m >> n;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] == 1) {
                q.push({ i,j });
                visit[i][j] = true;
            }
            else if (arr[i][j] == -1)
                visit[i][j] = true;
        }
 
    bfs();
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {
            if (visit[i][j] == 0) {
                cout << -1;
                return 0;
            }            
        }        
    cout << cnt;
    return 0;        
}