글 읽기 - 7576 시간 초과..(주석 있어요)

taehun0933 1년 전 0

한 3시간정도 열심히 풀었는데, 예외처리도 다 해주었는데 마지막에 시간 초과가 나서 너무 슬프네요..

풀이 시간쪽에서 개선 사항이 있을까요? 아예 갈아엎어야 할까요?

#include <bits/stdc++.h>
using namespace std;

int board[1001][1001];
bool isVisited[1001][1001];
bool isRipe = false; // 모두 익었는지를 판단하는 변수 선언
int day{0};
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
queue<pair<int, int>> Q;

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

    int m, n;
    cin >> m >> n;

    bool isInput0{true};
    // 처음 시작할 때 0값이 들어오지 않는다면, 토마토가 이미 익은 상태이므로 종료해주어도 됨. 그것을 판단하는 변수 선언

    for (int i{0}; i < n; i++)
        for (int j{0}; j < m; j++)
        {
            cin >> board[i][j];
            if (board[i][j] == 0)
                isInput0 = false;
        }

    while (!isRipe && !isInput0)
    {
        for (int i{0}; i < n; i++)
            for (int j{0}; j < m; j++)
            {
                if (!isVisited[i][j] && board[i][j] == 1)
                {
                    isVisited[i][j] = true;
                    Q.push({i, j});
                }
            }
        // board를 돌면서, 아직 방문하지 않은 1 값들을 모두 큐에 담는다. 이후, 이 값들을 바탕으로
        // 상하좌우로 0 값들을 1로 변경해 주면 된다.

        if (Q.empty()) // 큐가 비어있다는 것은, 하루가 지나도 토마토가 변함이 없다는 뜻임.
        {
            cout << -1;
            return 0;
        }
        int Qsize = Q.size();
        for (int i{0}; i < Qsize; i++)
        {
            int x, y;

            if (!Q.empty())
            {
                x = Q.front().first;
                y = Q.front().second;
                Q.pop();
            }

            for (int j{0}; j < 4; j++)
            {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if (nx < 0 || nx > n || ny < 0 || ny > m)
                    continue;
                else if (!isVisited[nx][ny] && board[nx][ny] == 0)
                    board[nx][ny] = 1;
            }
        } // 상하좌우로 0 값을 1로 변경해 주기

        // 이중for문으로, -1을 제외한 보드값이 모두 1인지 확인하기 : 하나라도 다르면 isRipe = false로 변경한다.
        isRipe = true;
        for (int i{0}; i < n; i++)
        {
            if (!isRipe)
                break;
            for (int j{0}; j < m; j++)
            {
                if (board[i][j] != -1 && board[i][j] == 0) // 값이 0이라는 것은, 아직 익지 못한 토마토가 있단 뜻
                {
                    isRipe = false;
                    break;
                }
            }
        }
        day++;
    }
    cout << day;
}

pill27211 1년 전 2

bfs를 포함한 전체 로직이 너무 비효율적입니다.

현재 while (!isRipe && !isInput0)의 매 사이클마다 최소(N * M) * 2만큼의 연산을 계속 추가로 하고 있고, N = 1000, M = 1000일 때를 생각하면 다소 무리가 있지요.

최초 1들의 위치를 큐에 먼저 넣는 건 정확한 발상인데 이는 '최초 한 번'이면 충분합니다. 매 사이클 마다 N * M을 돌며 추가해줄 필요가 전혀 없습니다.(bfs의 장점을 활용하지 못하고 있어요)

또한 마지막에서 n * m을 돌며 모두 1인지 확인하는 것 또한 bfs진행 후 '마지막에 한 번'이면 충분합니다.

bfs는 앞서 말씀 드린 최초 1들의 위치를 큐에 넣고, 큐가 빌 때까지 각 1들의 위치로부터 4방향 탐색을 진행하며 1의 영역을 점점 넓혀가면 됩니다.(그와 동시에 현재 영역이 방문된 시간을 기록하면서 진행하면 편리해요)

이후 마지막 체크 로직에서 문제가 없다면, 시간을 기록해둔 N * M배열에서 가장 큰 시간이 답이 되겠지요.

taehun0933 1년 전 0

감사합니다. 알려주신 개념에 대해 다시 한번 생각해보고 신중하게 코드를 짜니 바로 맞았어요. 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.