BOJ 2573 빙산 / BOJ 2295 세 수의 합 / BOJ 2493 탑 (DFS, 밋 인더 미들, 스택)

백준 BOJ 2573번 : 빙산

Solved.ac 난이도 : Gold IV

알고리즘 분류 : DFS

 

주어진 각 좌표에 빙산들의 높이가 주어지고, 빙산은 인접한 4개의 칸 중에서 물(즉, 높이가 0)인 칸들의 수만큼 단위 시간 1마다 감소한다고 할 때, 빙산이 두 덩어리로 분리되는데 걸리는 시간을 구하는 문제입니다.

 

우선은 빙산이 두 덩어리로 분리되는지 확인할 때 DFS가 필요합니다.

매 시간 턴마다 DFS를 수행하여 빙산이 분리되어 있는지 확인해줍니다.

 

그 다음 빙산을 녹일 때 앞 칸부터 빙산의 높이를 감소시켜버리면, 예를 들어 빙산의 높이가 0이 되어버리는 경우 다음 빙산의 높이 변화를 계산할 때 필요한 높이보다 1이 더 감소되어 버리게 됩니다.

(동시에 녹아야 하는데 앞 칸을 먼저 계산해서 뒷 칸이 잘못 계산된다는 의미)

따라서 melt 배열을 따로 선언하여 각 빙산마다 이번 턴에서 감소할 높이를 저장해주고, 해당 높이만큼 한 번에 감소시키는 방법을 사용하였습니다.

 

나머지는 구현이라서 코드의 길이만 길어질 뿐 크게 어려운 부분은 없습니다.

 

 

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

int N, M;
int arr[MAX][MAX], melt[MAX][MAX];
bool vis[MAX][MAX];

void DFS(int x, int y) {
    vis[x][y] = true;

    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    for(int i=0; i<4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;

        if(arr[nx][ny] > 0 && !vis[nx][ny]) DFS(nx, ny);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    cin >> N >> M;

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) cin >> arr[i][j];

    int year = 0;
    bool all_melt;

    while(true) {
        all_melt = true;
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                if(arr[i][j] > 0) all_melt = false;
        if(all_melt) break;

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++) vis[i][j] = false;

        int cnt = 0;
        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                if(arr[i][j] > 0 && !vis[i][j]) {
                    DFS(i, j);
                    cnt++;
                }

        if(cnt >= 2) break;


        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++) melt[i][j] = 0;

        int di[4] = {1, -1, 0, 0};
        int dj[4] = {0, 0, 1, -1};

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                if(arr[i][j] > 0) {
                    int melt_cnt = 0;

                    for(int k=0; k<4; k++) {
                        int ni = i + di[k];
                        int nj = j + dj[k];

                        if(ni < 0 || nj < 0 || ni >= N || nj >= M) continue;

                        if(arr[ni][nj] == 0) melt_cnt++;
                    }

                    melt[i][j] = melt_cnt;
                }

        for(int i=0; i<N; i++)
            for(int j=0; j<M; j++)
                arr[i][j] = max(arr[i][j] - melt[i][j], 0);

        year++;
    }

    if(all_melt) cout << "0\n";
    else cout << year << "\n";
}

 

 

백준 BOJ 2295번 : 세 수의 합

Solved.ac 난이도 : Gold IV

알고리즘 분류 : 밋 인더 미들

 

주어진 N개의 수 중에서 세 수를 합해서 역시 N개의 수에 포함되는 수를 만드는 경우들 중에서 가장 큰 값을 찾는 문제입니다.

(예를 들어 2, 3, 5, 10, 18의 경우 2 + 3 + 5 = 10을 만들 수도 있지만, 가장 큰 경우인 3 + 5 + 10 = 18을 찾으라는 의미)

 

문제에서 주어진 범위를 보면 N <= 1000이므로 브루트포스 알고리즘으로는 O(N^3)이므로 시간 초과가 발생하게 됩니다.

따라서 밋 인더 미들 알고리즘을 사용해서 풀이해주어야 합니다.

 

우선 2개의 수까지는 브루트포스로 조합시킬 수 있습니다. (1000^2 = 1,000,000이므로)

그 다음 이 100만개 이하의 합의 조합을 정렬시킨 뒤, upper_bound - lower_bound를 활용하여 주어진 N개의 수 중에서 하나가 존재하는지를 찾습니다.

 

제가 사용한 방법은, arr를 내림차순으로 정렬하고, 이중 for문에서 arr[i] - arr[j]를 값으로 가지는 두 수의 합이 존재한다면, 두 수의 합 + arr[j] = arr[i]가 되므로 순서쌍을 찾게 됩니다.

여기서 아까 arr를 내림차순으로 정렬하였으므로, 가장 먼저 찾은 순서쌍의 합이 답이 됩니다. (가장 크기 때문)

 

 

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];

    sort(arr.begin(), arr.end(), greater<int>());

    vector<int> sum(N*N);
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) sum[i*N + j] = arr[i] + arr[j];

    sort(sum.begin(), sum.end());

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            int diff = arr[i] - arr[j];
            int cnt = upper_bound(sum.begin(), sum.end(), diff) - lower_bound(sum.begin(), sum.end(), diff);

            if(cnt > 0) {
                cout << arr[i] << "\n";
                return 0;
            }
        }
}

 

 

백준 BOJ 2493번 : 탑

Solved.ac 난이도 : Gold V

알고리즘 분류 : 스택

 

높이가 다른 N개의 탑들이 수평으로 서 있고, 각 탑들은 왼쪽으로 레이저를 보내 다른 탑의 기둥(즉, 레이저를 맞은 탑의 높이가 더 높아야 함)으로 쏜다고 할 때, 각 탑의 레이저를 맞는 다른 탑의 위치를 순서대로 출력하는 문제입니다.

레이저가 아무 탑에도 맞지 않는다면 0을 출력해야 합니다.

 

이 문제는 스택을 활용하는 대표적인 예시 문제로, 앞에서부터 나온 탑의 높이들을 스택에 넣고, 현재 탑의 높이 이하인 것들을 pop 해주면서 앞의 나온 것들 중 가장 먼저 나오는(= 스택의 가장 위에 있는) 더 높은 탑의 위치를 출력해주면 됩니다.

탑의 위치를 출력해야 하기 때문에 Stack에 index와 height을 모두 저장할 수 있도록 pair에 대한 stack을 선언해줍시다.

 

만약 stack이 비었다면 그것은 현재 탑보다 앞에 더 높은 탑이 없다는 뜻이므로 0을 출력해주면 됩니다.

 

 

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    stack<pair<int, int>> S; // <index, height>

    for(int i=1; i<=N; i++) {
        int h; cin >> h;

        while(!S.empty()) {
            if(S.top().second > h) {
                cout << S.top().first << " ";
                break;
            }
            else S.pop();
        }

        if(S.empty()) cout << "0 ";

        S.push({i, h});
    }
}