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

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

7576번: 토마토

#문제 간단 정리

이 문제는 주어진 토마토의 상태에 따라 모든 토마토가 익게 되는 최소 일수를 찾는 문제입니다. 문제에서 요구하는 답을 찾기 위해 BFS(Breadth-First Search) 탐색 알고리즘을 사용합니다.

 

#전체 코드

#include <iostream>
#include <queue>
using namespace std;
int a[1000][1000];
int d[1000][1000];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

struct tomato {
    int x, y;
};

int main() {
    int n, m;
    cin >> m >> n;
    queue<tomato> q;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
            d[i][j] = -1;
            if (a[i][j] == 1) {
                q.push({i,j});
                d[i][j] = 0;
            }
        }
    }
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                if (a[nx][ny] == 0 && d[nx][ny] == -1) {
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx,ny});
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ans < d[i][j]) {
                ans = d[i][j];
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 0 && d[i][j] == -1) {
                ans = -1;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

 

#코드설명

코드 설명

• 변수 선언
  • a[1000][1000]: 각 토마토의 초기 상태를 저장하는 2D 배열
  • d[1000][1000]: 각 토마토가 익게 되는 데 걸리는 일수를 저장하는 2D 배열. 초기값은 -1로 설정
  • dx[], dy[]: 토마토의 인접한 위치를 찾기 위해 현재 위치에 더할 값들을 저장하는 배열
  • tomato: 토마토의 위치를 나타내는 구조체
• 입력 받기
  • m, n: 상자의 가로와 세로 크기
  • 상자의 토마토 상태를 입력 받으면서, 이미 익어 있는 토마토의 위치를 큐에 넣고, 해당 위치의 d[][] 값을 0으로 설정합니다.
• BFS 탐색
  • BFS 탐색을 시작합니다. 큐가 비어있지 않은 동안, 현재 토마토의 위치에서 인접한 네 방향을 확인하며 다음을 수행합니다:
    • 인접한 위치가 상자 내부에 있는지 확인합니다.
    • 인접한 위치의 토마토가 아직 익지 않았고, 방문하지 않은 상태라면, 현재 토마토가 익는 데 걸린 일수에 1을 더한 값을 인접한 위치의 토마토가 익는 데 걸리는 일수로 설정합니다.
    • 인접한 위치의 토마토를 큐에 넣습니다.
• 결과 찾기
  • BFS 탐색이 끝나면, d[][] 배열에서 가장 큰 값을 찾아 ans에 저장합니다. 이 값이 모든 토마토가 익게 되는 데 필요한 최소 일수입니다.
  • 하지만, 상자 안에 아직 익지 않은 토마토가 있는지 확인하고, 있다면 -1을 출력해야 합니다. 이를 위해 a[][] 배열을 탐색하며 아직 익지 않은 토마토가 있는지 확인합니다. 익지 않은 토마토가 있으면 ans 값을 -1로 설정합니다.
• 결과 출력
  • ans 값을 출력합니다.

이 코드는 BFS 탐색을 사용하여 모든 토마토가 익게 되는 최소 일수를 효율적으로 찾습니다.