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

문제 : 

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

7576번: 토마토

 

 

 

 

간단 풀이 : 

 

1) 토마토을 입력받으면서

    - 익은 토마토(1)가 들어온다면 q에 넣고 dis를 0으로 설정한다.

    - 익어야하는 토마토(0)이 들어온다면 dis를 -1으로 설정한다.

 

2) 전형적인 bfs의 while문을 돌린다.

   - 범위를 벗어나거나 -1이 아니라면(익지않은 토마토에서 값이 변경된경우) continue한다.

   - 새로운 위치의 dis를 원래 위치의 dis+1 을 저장한다.

 

3) 토마토들을 돌면서

    -  -1(익지않은 토마토)이 있다면 익지않은 토마토가 존재하는 것이므로 -1을 출력해준다.

    -  max를 이용해서 dis값의 최댓값을 구해 출력한다.

 

 

 

 

 

문제 코드 : 

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int, int> P;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int mp[1001][1001];
int dis[1001][1001];

queue<P>q;
int main() {
    int n, m;
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> mp[i][j];
            if (mp[i][j] == 1) { // 익은 토마토 => dis == 0
                q.push({ i,j });
                dis[i][j] = 0;//모든 토마토가 익어있다면 0을 출력해야하므로
            }
            if (mp[i][j] == 0) { // 익혀야하는 토마토 => dis=-1
                dis[i][j] = -1;
            }

        }
    }
    while (!q.empty()) {
        P cur = q.front();
        q.pop();
        for (int dir = 0; dir < 4; dir++) {
            int nx = dx[dir] + cur.x;
            int ny = dy[dir] + cur.y;
            if (nx < 0 || nx >= n|| ny < 0 || ny >= m) continue;
            if (dis[nx][ny] != -1) continue;
            dis[nx][ny] = dis[cur.x][cur.y] + 1;
            q.push({ nx,ny });
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dis[i][j] == -1) { // 익혀야하는 토마토가 남아있다면
                cout << -1;
                return 0;
            }
            ans = max(ans, dis[i][j]);
        }
    }
    cout << ans;
}

 

 

너무나도 유명한 문제

풀때마다 약간씩 헷갈린다.

 

처음 토마토를 입력받을때 1이면 큐에 넣고, dis를 0으로 초기화

0이면 dis를 -1으로 초기화

 

while문에서 dis가 -1이 아니라면 continue; 이정도만 알면 될것같다!