글 읽기 - 빙산(2573) c++

soom9611 3년 전 0

스택 이용한 DFS 사용해서 풀었는데 틀린 부분을 못찾겠습니다..ㅠ
//  빙산 (https://www.acmicpc.net/problem/2573)

#include <iostream>
#include <stack>
#include <cstring>

#define MAX 300

using namespace std;

int N, M;
int iceberg[MAX][MAX];
int visited[MAX][MAX];
int dx[4] = { 1, 0, -1, 0};
int dy[4] = { 0, 1, 0, -1 };

/**
 * 1. DFS를 사용해서 빙산이 몇 덩어리인지 확인한다.
 * 2-1. 2덩어리 미만이면 year + 1 하고, 1년 후 녹은 빙산의 현황을 저장한다.
 * 2-2. 2덩어리 이상이면 year를 출력하고 return
 * 다 녹을때까지 반복
 */
void melt() {
    int newIceberg[MAX][MAX];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (iceberg[i][j] == 0) // 빙산이 없다면 continue
                continue;

            // (i, j) 위치에는 빙산이 있다.
            int adj = 0; // 바닷물이 얼마나 인접해있는지 저장하는 변수
            for (int dir = 0; dir < 4; dir++) {
                int nextX = i + dx[dir];
                int nextY = j + dy[dir];

                if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || iceberg[nextX][nextY] != 0) // 범위를 벗어났거나, 인접한 곳이 빙산이라면 continue
                    continue;

                adj++;
            }

            if (iceberg[i][j] - adj <= 0) {
                newIceberg[i][j] = 0;
            }
            else {
                newIceberg[i][j] = iceberg[i][j] - adj;
            }
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            iceberg[i][j] = newIceberg[i][j];
        }
    }
}

// DFS 사용
int getIcebergNum() {
    int answer = 0;

    memset(visited, 0, sizeof(visited)); // visited 배열 0으로 초기화
    stack<pair<int, int>> S;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (visited[i][j] == 0 && iceberg[i][j] != 0) {
                S.push({ i, j });
                visited[i][j] = 1;

                // DFS
                while (!S.empty()) {
                    int curX = S.top().first;
                    int curY = S.top().second;
                    S.pop();

                    for (int dir = 0; dir < 4; dir++) {
                        int nextX = curX + dx[dir];
                        int nextY = curY + dy[dir];

                        if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || visited[nextX][nextY] != 0) // 범위를 벗어나거나 이미 방문한 곳이라면 continue
                            continue;

                        if (iceberg[nextX][nextY] != 0) { // 아직 방문하지 않았고, 빙산이 있는 위치라면
                            S.push({ curX, curY });
                            S.push({ nextX, nextY });
                            visited[nextX][nextY] = 1;

                            break;
                        }
                    }
                }

                answer++;
            }
        }
    }

    return answer;
}

bool isAllIceberg() {
    bool ans = true;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (iceberg[i][j] == 0) {
                return false;
            }
        }
    }

    return ans;
}

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

    // input
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> iceberg[i][j];
        }
    }
    
    // solve
    int year = 0;
    
    while (true) {
        if (isAllIceberg()) {
            cout << "0\n";
            break;
        }

        int curIceberg = getIcebergNum();

        if (curIceberg >= 2) { // 빙산이 두 덩어리 이상으로 분리되었으면
            cout << year << "\n"; // year를 출력하고 break
            break;
        }
        else if (curIceberg == 0) { // 빙산이 다 녹았을 경우
            cout << "0\n"; // year를 출력하고 break
            break;
        } 

        // 빙산이 한 덩어리고 아직 다 안녹았을 경우
        year++;
        melt();
    }

    return 0;
}
댓글을 작성하려면 로그인해야 합니다.
문제

문제

출처

ICPC

빙산(2573) c++

soom9611 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
