[BOJ 7576] (DFS/BFS) 토마토 (C++) - (최적화)

토마토(Silver 1)

문제

전체 문제 보기

7576번: 토마토

접근법

이 문제는 7569번 토마토 문제와 동일하다. 7569번 토마토 문제는 3차원 공간에서 BFS로 풀이하는 문제이고 이번 문제는 오히려 조금 더 쉬운 2차원 공간에서 BFS로 풀이하는 문제이다. 그래서 접근법에 대한 설명은 7569번 토마토 풀이글을 참고하자

최적화

7569번 토마토 문제 풀고 조금 더 쉬운 이번 문제를 다시 풀게되어 이번에는 조금 더 시간을 줄일 수 있도록 최적화 부분에 조금 더 신경을 써보게 되었다. 그 결과 기존 풀이에서 107,912KB / 340ms 나오던 결과를 60,892KB / 200ms 까지 줄일 수 있었다. 어떤 부분에서 성능을 줄일 수 있었는지 살펴보고 다음 풀이에서 반영하도록 해야겠다.

기본적으로 이 알고리즘의 시간복잡도와 공간 복잡도는 \(O(N \cdot M) \) 이다. 최적화를 하더라도 이는 변함이 없는 부분이다. 모든 노드에서 반복 작업을 하는 것을 일부 노드에서는 생략할 수 있도록 하거나, 모든 노드에 10번 할 일을 1번 만에 하도록 일의 양을 줄이거나 중복 작업을 줄여 성능을 향상하는 것이 중점을 두었다. 아래는 기존 코드에서 문제를 느낀 부분이다.

• 인접 노드를 동적 배열로 사용하여 발생한 빈번한 push_back
• 시작 노드를 탐색하기 위해 이중으로 전체 노드를 탐색
• 토마토가 없는 공간에도 굳이 노드를 생성하여 불필요한 자원낭비

그리고 추가적으로 코드의 가독성을 위해서 클래스로 추상화를 진행하였다.

인전 노드 정적배열로 수정

여기서 인접 노드는 최대 4개까지 사용된다. 하지만 기존 코드에서 인접 노드를 동적 배열로 선언하고 인접 노드주소를 추가하기 위해 push_back을 사용하였다. 물론 reserve 함수를 통해서 4개의 원소를 미리 할당했지만, [] 연산을 사용하는것 보다는 느리다. 그리고 문제의 이 코드는 전체 노드에서 최대 4번씩 호출되기 때문에 가장 많이 호출되는 부분이다. 때문에 이 부분의 성능 개선이 가장 중요했다. 때문에 인접 노드를 array로 사용하거나 resize 함수를 통해서 push_back이 아닌 [] 연산으로 값을 입력받을 수 있도록 개선하는 작업이 필요했다. 여기서는 array로 인접노드 컨테이너를 개선하였고, push_back을 []연산자로 모두 수정하였다. 테스트 결과 107,912KB / 340ms 에서 61,036KB / 212ms로 가장 큰 성능 개선 효과를 보였다.

// 인접노드 연결 부분
    for (int n = 0; n < N; ++n)
    {
        for (int m = 0; m < M; ++m)
        {
            if (map[n][m] == nullptr) continue;

            if (n > 0)
            {
                map[n][m]->mAdjacent[0] = map[n - 1][m];
            }
            if (n < N - 1)
            {
                map[n][m]->mAdjacent[1] = map[n + 1][m];
            }

            if (m > 0)
            {
                map[n][m]->mAdjacent[2] = map[n][m - 1];
            }
            if (m < M - 1)
            {
                map[n][m]->mAdjacent[3] = map[n][m + 1];
            }
        }
    }

불필요한 중복 탐색 삭제

전체 데이터를 입력한 후 시작 노드를 정하기 위해서 BFS 함수내에서 다시 전체 노드를 탐색하는 부분이 있다. 데이터를 입력하는 과정에서 if(num ==1) 부분이 있음에도 BFS에서 다시 if(node->mNum == 1) 이렇게 중복으로 비교연산을비교 연산을 진행했다. 그래서 데이터를 입력하는 과정에서만 비교 연산을 진행하고 초기값을 데이터 입력 과정에서 삽입할 수 있도록 개선하였다. 그 결과 61,036KB / 212ms에서 61,040KB / 196 ms 로 16ms정도 성능 향상을 보였다.

필요한 노드만 생성

문제에서 토마토가 없는 경우도 존재한다. 그러나 풀이에서는 굳이 이런 칸에도 노드를 생성해서 -1로 토마토가 없음을 표시했다. 실제로 토마토가 없는 노드의 경우 인접노드로 연결할 필요도 없기 때문에 사용될 일이 없다. 그래서 굳이 노드를 생성할 필요가 없었다. 그래서 데이터를 입력받는 과정에서 토마토가 없는 경우를 확인하고, 토마토가 있는 경우에만 노드를 생성하였다. 그리고 인접 노드 연결 과정에서 노드가 nullptr인 경우 예외처리를 추가했다.

 

그 결과 61,040KB / 196 ms 이던 성능이 60,892KB / 200ms로 메모리 공간 사용량은 줄었지만 모든 노드에서 비교문이 증가하며 속도는 조금 줄어든 모습을 보였다. 이 부분에서는 자원과 시간 사이의 트레이드오프가 발생함을 확인하였다.

전체 소스코드

#include <iostream>
#include <array>
#include <queue>
#define endl '\n'
using namespace std;

struct Node {
    Node(int mNum)
        : mAdjacent{}, mNum(mNum)   // 모든 노드는 노드에 할당된 번호를 0으로 초기화.
    {
    }
    array<Node*, 4> mAdjacent;    // 인접 노드에 대한 정보, 상하좌우 4방향
    int mNum;                   // 토마토 깊이 정보 (1 이상: 익은 토마토, 0: 익지 않은 토마토)
};
// 박스를 표현하기 위한 맵
using NodeMap = array<array<Node*,1'000>,1'000>;

class Tomato {
public:
    Tomato(int _M, int _N) : M(_M), N(_N), map{}, numTomato(0)
    {}
    ~Tomato();
    void InputData();
    void ConnectAdjacent();
    int BFS();

private:
    NodeMap map;
    queue<Node*> q;
    int M, N;
    int numTomato;
};
void Tomato::InputData()
{
    for (int n = 0; n < N; ++n)
    {
        for (int m = 0; m < M; ++m)
        {
            int num;
            cin >> num;
            if (num == -1) continue;
            map[n][m] = new Node(num);
            if (num == 1)
                q.push(map[n][m]);
            numTomato++;
        }
    }
}
void Tomato::ConnectAdjacent()
{
    for (int n = 0; n < N; ++n)
    {
        for (int m = 0; m < M; ++m)
        {
            if (map[n][m] == nullptr) continue;

            if (n > 0)
            {
                map[n][m]->mAdjacent[0] = map[n - 1][m];
            }
            if (n < N - 1)
            {
                map[n][m]->mAdjacent[1] = map[n + 1][m];
            }

            if (m > 0)
            {
                map[n][m]->mAdjacent[2] = map[n][m - 1];
            }
            if (m < M - 1)
            {
                map[n][m]->mAdjacent[3] = map[n][m + 1];
            }
        }
    }
}
int Tomato::BFS()
{
    int answer = 0;

    // 큐가 빌때까지 탐색 시작
    Node* cur;
    while (!q.empty())
    {
        cur = q.front();
        q.pop();
        numTomato--;

        for (auto neighbor : cur->mAdjacent)
        {
            if (neighbor == nullptr) continue;
            if (neighbor->mNum == 0)
            {
                neighbor->mNum = cur->mNum + 1;
                q.push(neighbor);

                answer = neighbor->mNum - 1;
            }
        }
    }
    // 탐색 종료후에 토마토가 남았다면 -1 반환
    if (numTomato > 0)
        answer = -1;
    return answer;
}
Tomato::~Tomato()
{
    for (int n = 0; n < N; ++n)
    {
        for (int m = 0; m < M; ++m)
        {
            if (map[n][m] == nullptr) continue;
            // 동적할당한 노드 삭제
            delete map[n][m];
        }
    }
}

int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    // M: 가로 (2 ~ 1000)
    // N: 세로 (2 ~ 1000)
    int M, N;

    cin >> M >> N;

    Tomato tomato(M, N);
    tomato.InputData();
    tomato.ConnectAdjacent();

    int answer;
    answer = tomato.BFS();

    cout << answer;

    return 0;
}