글 읽기 - 7576 c++ 질문드립니다.

dohoon88 2년 전 0

예제 케이스는 모두 결과가 잘 출력되는데, 틀렸다고 나오네요ㅠ 도움 주시면 감사하겠습니다!

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#define MAX 1000

using namespace std;

typedef tuple<int, int> INDEX;

int M, N;
int tomatoes[MAX][MAX];
int visited[MAX][MAX];
queue<INDEX> q;
int zeros;
int result;

bool isZeroAdj(int x, int y) {
    return
        x >= 0 &&
        x <= N - 1 &&
        y >= 0 && 
        y <= M - 1 &&
        !visited[x][y] &&
        !tomatoes[x][y];
}

vector<INDEX> getZeroAdj(INDEX idx) {
    int x = get<0>(idx);
    int y = get<1>(idx);
    vector<INDEX> result;
    if (isZeroAdj(x - 1, y)) result.push_back(make_tuple(x - 1, y));
    if (isZeroAdj(x, y - 1)) result.push_back(make_tuple(x, y - 1));
    if (isZeroAdj(x, y + 1)) result.push_back(make_tuple(x, y + 1));
    if (isZeroAdj(x + 1, y)) result.push_back(make_tuple(x + 1, y));
    return result;
}

void bfs() {
    while (1) {
        int size = q.size();
        int cnt = 0;
        while (cnt < size) {
            INDEX front = q.front();
            int frontX = get<0>(front);
            int frontY = get<1>(front);
            vector<INDEX> adjs = getZeroAdj(front);
            for (INDEX adj: adjs) {
                int adjX = get<0>(adj);
                int adjY = get<1>(adj);
                visited[adjX][adjY] = true;
                q.push(adj);
            }
            q.pop();
            cnt++;
        }
        if (q.empty()) break;
        
        for (int i = 0; i < q.size(); i++) {
            INDEX front = q.front();
            int frontX = get<0>(front);
            int frontY = get<1>(front);
            tomatoes[frontX][frontY] = 1;
            q.push(front);
            q.pop();
        }
        result++;
    }
}

int main() {
    cin >> M >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) cin >> tomatoes[i][j];
    }

    zeros = 0;
    result = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (!tomatoes[i][j]) {
                bool isolated = true;
                if (i >= 1 && tomatoes[i - 1][j] != -1) isolated = false;
                if (j >= 1 && tomatoes[i][j - 1] != -1) isolated = false;
                if (j < M - 1 && tomatoes[i][j + 1] != -1) isolated = false;
                if (i < N - 1 && tomatoes[i + 1][j] != -1) isolated = false;
                if (isolated) {
                    cout << -1 << endl;
                    return 0;
                }
                zeros++;
            }
            visited[i][j] = false;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (tomatoes[i][j] == 1) {
                visited[i][j] = true;
                q.push(make_tuple(i, j));
            }
        }
    }

    bfs();

    cout << result << endl;
    return 0;
}

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

문제

문제

출처

ICPC

7576 c++ 질문드립니다.

dohoon88 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말