Written by JS970
on March 24, 2023

7576 - 토마토

난이도: 골드 5
날짜: 2023년 3월 24일
상태: Correct
추가 검토 여부: Todo Implement with Graph Theory(BFS)
알고리즘 : Graph(BFS), heuristic(?)

나중에 BFS를 이용하여 풀이 시도해 볼 것

Solution

보자마자 그래프 문제인 것은 알았지만 어떻게 풀어야 할지 감이 잡히지 않았다.
그냥 내가 짠 알고리즘대로 풀이에 도전했고, 초기 코드는 시간복잡도로 인한 시간초과 문제가 있었으나 해결했다.
아래는 내 접근법이다.
1. 오늘 익은 토마토만이 내일 익을 토마토에 영향을 미친다. 이처럼 다음 익을 토마토에 영향을 미칠 토마토들의 배열 인덱스를 저장하는 nextRipeQueue를 이용한다.
2. nextRipeQueue에 인접한 상하좌우 위치의 토마토에 대해(배열 원소값이 -1이거나, 배열 경계를 벗어난 경우는 처리하지 않는다.) 1로 바꾸는 propagate작업을 한다. 이 작업은 문제 조건에 따라 하루에 한 번 일어난다.
3. propagate작업을 수행했음에도 불구하고 익은 토마토의 개수가 변하지 않는 경우 익을 수 있는 모든 토마토가 다 익은 것이다. 이때, 익을 수 없는 위치에 토마토가 존재하는 예외 상황에 대해서 처리해 주어야 한다.(총 토마토 개수와 익은 토마토 개수의 개수 비교로 구현 가능)
결과적으로 접근법 자체는 틀리지 않았으나, 익지 않은 토마토의 개수를 세는 함수를 따로 구현하여 정답을 계산하는 함수에서 호출하였더니 불필요한 연산이 증가함에 따라 시간초과를 출력했다.
- 불필요한 연산을 제거하니 문제는 해결되었다.

code

윗 문단에서 소개한 내 접근법으로 구현한 코드

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

int propagate(int ** arr, int M, int N, queue<pair<int, int>> * q)
{
    int result = 0;
    int dc[4] = {1, 0, -1, 0};
    int dr[4] = {0, 1, 0, -1};
    vector<pair<int, int>> nextRipe;

    while(!(q->empty()))
    {
        int c = q->front().first; int r = q->front().second;
        for(int i = 0; i < 4; i++)
        {
            int col = c + dc[i]; int row = r + dr[i];
            if(col < 0 || row < 0 || col >= N || row >= M) continue;
            if(arr[col][row] == -1) continue;
            if(arr[col][row] == 0)
            {
                arr[col][row] = 1;
                nextRipe.push_back({col, row});
                result++;
            }
        }
        q->pop();
    }
    for(int i = 0; i < nextRipe.size(); i++)
        q->push(nextRipe[i]);
    return result;
}

int dayCalc(int ** arr, int M, int N, queue<pair<int, int>> q)
{
    int result = 0;
    int curCount = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            if(arr[i][j] == 0) curCount++;
    if(curCount == 0) return result;
    int prevCount = 0;
    int tomato = 0;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
            if(arr[i][j] != -1) tomato++;
    prevCount = curCount;
    
    while(true)
    {
        curCount -= propagate(arr, M, N, &q);
        if(curCount == prevCount)
        {
            int ripedTomato = 0;
            for(int i = 0; i < N; i++)
                for(int j = 0; j < M; j++)
                    if(arr[i][j] == 1) ripedTomato++;
            if(ripedTomato == tomato) return result;
            return -1;
        }
        prevCount = curCount;
        result++;
    }
}

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

    int M, N;
    cin >> M >> N;
    int ** arr = new int*[N];
    queue<pair<int, int>> nextRipeQueue;
    for(int i = 0; i < N; i++)
    {
        arr[i] = new int[M];
        for(int j = 0; j < M; j++)
        {
            cin >> arr[i][j];
            if (arr[i][j] == 1) nextRipeQueue.push({i, j});
        }
    }

    cout << dayCalc(arr, M, N, nextRipeQueue) << endl;
    return 0;
}

ref

7576번: 토마토

Top