7576번 - 토마토

문제

입출력

풀이

너비 우선 탐색을 통해 최소 날짜 구하기

• 입력받은 토마토에서 익지 않는 것이 있을 경우 -1 출력
• 입력받은 토마토가 이미 모두 익어있으면 0 출력

→ -1이 입력되면 이미 방문한것으로 취급하여 너비 우선 탐색 진행

#include <iostream>
#include <queue>
using namespace std;

const int MAX = 1001;
int M, N; // 가로 세로
int map[MAX][MAX]; // 최단 거리 저장
bool visit[MAX][MAX]; // 방문했는지 확인
int input[MAX][MAX]; // 처음 입력받는 토마토 상태
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
queue<pair<int, int>> q;

void BFS() {
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < N && ny >= 0 && ny < M) {
                if (visit[nx][ny] == 0) { // 방문하지 않았을 경우
                    map[nx][ny] = map[x][y] + 1; // map[x][y]에서 1 증가
                    visit[nx][ny] = true; // 방문한 것으로 체크
                    q.push({nx,ny}); // 큐에 삽입하여 재귀
                }
            }
            
        }
    }

}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie();

    cin >> M >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> input[i][j];
            if (input[i][j] == 1) { // 익은 토마토가 있는 곳
                map[i][j] = 0; // 처음 거리는 0
                visit[i][j] = true; // 방문한 것으로 체크
                q.push({i,j}); // 큐에 삽입하여 BFS 시작점
            }
            else if (input[i][j] == -1) {
                visit[i][j] = true; // 만약 토마토가 없는 곳은 이미 방문한 것으로 하여 경계선 생성
            }
        }
    }
    BFS(); // 너비 우선 탐색

    int ans = -1; 
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 0 && input[i][j] == 0) { // 만약 너비 우선 탐색 후에 토마토가 있는 곳에 최단 거리가 0인 경우 익지 않은 토마토가 있는 것으로 확인
                cout << -1;
                return 0;
            }
            if (map[i][j] > ans) {
                ans = map[i][j]; // 가장 큰 최단 거리를 구함
            }
        }
    }

    cout << ans;

}

2023.07.07 - [Problem Solving/C++] - 14940번 - 쉬운 최단거리