240514: 굿바이 클래스 3. 테트로미노, DEPQ(이중-우선순위 큐)

2024-05-14

Good bye CLASS 3

지금까지 클래스 3 금장 풀이와 이산수학 공부에 집중했다. 클래스 3 금장까지 하나의 문제만을 남겨뒀다.
대체적으로 이제 골드 하위 문제도 꽤 잘 푸는 것 같아서 기분이 좋다. 특히 그래프 탐색류의 문제들은 내가 제일 잘 푸는 것 같다. (골드 BFS/DFS 문제도 실버같다는 생각이 든다)

CLASS 3 문제 정리

푼 문제:

• 카잉 달력 (실버 1 - 6064)
• 경로 찾기 (실버 1 - 11403)
• 가장 가까운 세 사람의 심리적 거리 (실버 1 - 20529)
• 테트로미노 (골드 4 - 14500)
• 리모컨 (골드 5 - 1107)
• AC (골드 5 - 5430)
• 적록색약 (골드 5 - 10026)
• 이중 우선순위 큐 (골드 5 - 7662)

카잉 달력 (실버 1 - CRT, 정수론, 브루트포스)

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

카잉 달력은 단순화해서 M:N 진수의 시계 체계에서 M과 N이 주어졌을 때 x:y가 몇 번째 해를 나타내는지 구하는 문제.

CRT (중국인의 나머지 정리)를 이용해서 푸는 방법이 있고. 나처럼 최적화된 브루트포스를 이용해서 푸는 방법이 있다.

나는 최적화 브루트포스를 통해서 풀었고. 문제를 잘못 이해해서 삽질을 조금 한 것을 빼면 무난하게 풀었다.
CRT는 나중에 본격적으로 알아보기로 했다. (수학적 개념이 들어간 정리라서, 이산 수학 책을 모두 정리하고 알아보고 싶었다)

이 문제를 처음 읽고 나서는 x:y에서 시작할 때 M:N까지 걸리는 시간을 구하는 줄 알았다. 근데 문제의 요구사항은 <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하는 것이었고. 로직은 완벽하게 구현했지만, 문제 이해에서 틀린 케이스다.

따라서 M:N이라고 할 때 0:0에서 멸망해까지 걸리는 시간은 M과 N의 LCM(최소공배수)다.
즉 내가 구한 답은 x:y에서 LCM(M, N) 까지 걸리는 시간이었기 때문에.
LCM(M, N) - <x:y>로 문제의 요구사항을 충족시켰다.

브루트포스로 푼다면 어렵지 않은 문제였다.

// 백준: 카잉 달력
// https://www.acmicpc.net/problem/6064
// 2024-04-30

#include <iostream>
using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) {
    while (b != 0) {
        ll t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
    int T;
    cin >> T;
    while (T--) {
        int M, N, x, y;
        cin >> M >> N >> x >> y;
        ll max = lcm(M, N);
        int cnt = 0;
        while (true) {
            int dx = M - x;
            int dy = N - y;
            if (dx > dy) { // y가 M에 더 빨리 도달
                y = N;
                x += dy;
                cnt += dy;
            } else if (dx < dy) { // x가 N에 더 빨리 도달
                x = M;
                y += dx;
                cnt += dx;
            } else { // 동시에 도달한다면
                cnt += dx;
                cout << max - cnt << "\n";
                break; // 멸망해
            }

            if (x == M && y == N) {
                cout << max - cnt << "\n";
                break; // 멸망해
            }

            cnt++;
            x = (x % M) + 1;
            y = (y % N) + 1;

            if (cnt > max) {
                cout << "-1\n";
                break;
            }
        }
    }
}

---

경로 찾기 (실버 1 - 플로이드 워셜 그래프)

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

입력:
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.

플로이드 워셜의 인접 행렬과 유사한 입력이 들어온다. 이 문제에서는 경로의 존재 여부만 판단하면 되기 때문에, 단순히 플로이드 워셜 탐색을 돌리면서 경로가 존재하면 1, 존재하지 않으면 0으로 표시하면 된다.

주의할점은, 플로이드 워셜을 구현할 때 거쳐가는 노드 k는 항상 최 외부 반복문에 있어야 한다.
내부 반복문에 있으면 어떤 경로간에서 가능한 거쳐가는 노드 케이스를 모두 탐색하지 못한 채로 다른 경로로 넘어가기 때문에, 이미 이전 경로의 해가 최적화되지 않은 상태에서 탐색을 이어가게 된다. 즉 정확도 오류가 난다.

// 백준: 경로 찾기
// https://www.acmicpc.net/problem/11403
// 2024-05-07

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // 주의: 방향 그래프
    int N; // 정점의 개수 N
    cin >> N;
    vector<vector<int>> adj(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> adj[i][j];
        }
    }

    for (int k = 1; k <= N; ++k) {
        for (int i = 1; i <= N; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (adj[i][k] && adj[k][j]) // i -> k -> j 가 가능하다면 (1이라면)
                    adj[i][j] = 1;
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cout << adj[i][j] << " ";
        }
        cout << "\n";
    }

    return 0;
}

부가 설명:

Floyd-Warshall 알고리즘을 구현할 때, 거쳐가는 노드 𝑘는 항상 최외부 반복문에 있어야 합니다. 이를 통해 모든 가능한 중간 노드를 고려한 후 각 경로를 최적화할 수 있습니다. 내부 반복문에 𝑘가 위치하면 모든 경로에 대해 올바른 경로 계산이 이루어지지 않을 수 있습니다.

---

가장 가까운 세 사람의 심리적 거리 (실버 1 - 비둘기집 원리)

인원 수 N, 그리고 각 인원의 MBTI 유형이 주어질 때. 가장 작은 거리를 가지는 세 사람의 거리를 구하는 문제.
MBTI간의 거리는 척도 차이의 수로 정의한다.

즉, ENTP <-> ENFP의 심리적 거리는 1.

이 문제는 정말 단순한 브루트포스 문제다. 그냥 3중 for문으로 가능한 모든 조합에 대해 최소 거리를 구하면 된다.

하지만, 입력으로 주어질 수 있는 최대 N이 100,000명이다. 10만명에 대해 가능한 모든 조합을 조사하면 무조건 TLE가 난다.

정말 상식적인건데 쉽게 잊는 명제가 있다. 바로 비둘기집 원리. MBTI의 유형 개수가 총 16개이기 때문에. 인원수가 17명 이상이라면 무조건 두명 이상은 같은 MBTI를 가진다.

인원수가 33명 이상이라면 무조건 세명 이상은 같은 MBTI를 가진다. 즉 N > 32 일때 답은 무조건 0이다.

이를 이용해서 브루트포스를 최적화 할 수 있고. 비둘기집 원리를 겨냥한 문제다.

// 백준: 가장 가까운 세 사람의 심리적 거리
// https://www.acmicpc.net/problem/20529
// 2024-05-07

/*
1. 브루트포스 사용
2. N이 32 초과라면, 답은 무조건 0임 (비둘기집의 원리)
MBTI의 유형 수는 총 16개고, 인원이 17명이라면 하나의 유형은 최소 2명 이상의 공통 MBTI를 가진다.
*/

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int getDiff(string a, string b) {
    int diff = 0;
    for (int i = 0; i < 4; ++i) {
        if (a[i] != b[i])
            ++diff;
    }
    return diff;
}

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

    int TC;
    cin >> TC;
    while (TC--) {
        int N; // 학생의 수
        cin >> N;

        vector<string> mbtis(N);

        // 입력
        for (int i = 0; i < N; ++i) {
            string mbti;
            cin >> mbti;
            mbtis[i] = mbti;
        }

        // 비둘기집의 원리 필터링
        if (N > 32) {
            cout << "0\n";
            continue;
        }

        // 계산
        int minDistance = (~0U >> 2);
        for (int i = 0; i < N; ++i) {
            for (int j = i + 1; j < N; ++j) {
                for (int k = j + 1; k < N; ++k) {
                    int cur_dist = getDiff(mbtis[i], mbtis[j]) + getDiff(mbtis[j], mbtis[k]) + getDiff(mbtis[i], mbtis[k]);
                    if (cur_dist < minDistance)
                        minDistance = cur_dist;
                }
            }
        }

        cout << minDistance << "\n";
    }
}

---

테트로미노 (골드 4 - 구현, 도형)

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다.

정사각형은 서로 겹치면 안 된다.
도형은 모두 연결되어 있어야 한다.
정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다.
정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 한다.

아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다.

테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오.

테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다.

테트로미노의 종류는 위의 5가지다. 위 5개의 도형을 회전/대칭해서 점수판 위에 올려놨을 때. 가질 수 있는 가장 많은 점수를 출력하는 문제.

처음엔 DFS/BFS를 활용해서 풀 수 있다고 생각했으나, 'ㅗ' 의 처리가 곤란해서 실행하지 않았다.
이제 와서 생각해보면, 'ㅗ' 은 따로 처리하고, 나머지 4개에 대해서 DFS로 처리했다면 쉬웠을 것 같다.

결론적으로 내가 푼 방식은 위 사진의 기본 테트로미노 모양 5개를 저장해놓고, 회전/대칭 함수를 만든 뒤 가능한 모든 변형에 대해 배열에 저장하고 브루트포스로 풀었다.

실수하기 쉬운 복잡한 구현 문제였다.
도형의 회전은: 전치 -> 수평 뒤집기 -> 절댓값 좌표 변환 순으로 했다.

// 백준: 테트로미노
// https://www.acmicpc.net/problem/14500
// 2024-05-09

/*
그냥 단순 구현 브루트포스?
모든 퍼즐에 대해 회전/대칭 절대좌표 구하기
1. 회전, 대칭후 절대좌표로 변환
2. 브루트포스
*/

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

struct Piece {
    int x;
    int y;
};

vector<Piece> transpose(const vector<Piece> &pieces) { // 전치
    vector<Piece> transposed;
    for (const auto &piece : pieces) {
        transposed.push_back({piece.y, piece.x});
    }
    return transposed;
}

vector<Piece> flipHorizontal(const vector<Piece> &pieces, int M) { // 수평 뒤집기
    vector<Piece> flipped;
    for (const auto &piece : pieces) {
        flipped.push_back({piece.x, M - 1 - piece.y});
    }
    return flipped;
}

vector<Piece> flipVertical(const vector<Piece> &pieces, int M) { // 수직 뒤집기
    vector<Piece> flipped;
    for (const auto &piece : pieces) {
        flipped.push_back({M - 1 - piece.x, piece.y});
    }
    return flipped;
}

vector<Piece> absolute(const vector<Piece> &pieces) {
    // 각 x y 좌표의 최소값 빼기: (0, 0) 기준 맞추기
    vector<Piece> absoluted;
    int minX = (~0U >> 2);
    int minY = (~0U >> 2);
    for (const auto &piece : pieces) {
        minX = min(minX, piece.x);
        minY = min(minY, piece.y);
    }

    for (const auto &piece : pieces) {
        absoluted.push_back({piece.x - minX, piece.y - minY});
    }

    return absoluted;
}

vector<Piece> rotate90Degrees(const vector<Piece> &pieces, int M) {
    // 전치 -> 수평 뒤집기 -> 절댓값 변환
    vector<Piece> transposed = transpose(pieces);
    vector<Piece> flipped = flipHorizontal(transposed, M);
    vector<Piece> absoluted = absolute(flipped);

    return absoluted;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // 맵 입력받기
    int N, M;
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(M, 0));
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> map[r][c];
        }
    }

    // 테트로미노 기본 정보 (5 종류)
    vector<Piece> puzzle_straight = {{0, 0}, {0, 1}, {0, 2}, {0, 3}};
    vector<Piece> puzzle_square = {{0, 0}, {0, 1}, {1, 0}, {1, 1}};
    vector<Piece> puzzle_ㄱ = {{0, 0}, {0, 1}, {0, 2}, {1, 0}};
    vector<Piece> puzzle_ㄹ = {{0, 2}, {0, 1}, {1, 1}, {1, 0}};
    vector<Piece> puzzle_ㅜ = {{0, 1}, {1, 1}, {1, 0}, {2, 1}};

    // 모든 조합의 퍼즐 정보
    vector<vector<Piece>> puzzles;

    // 퍼즐 집합 저장
    puzzles.push_back(puzzle_straight); // 1. 직선 (회전 1회만)
    puzzles.push_back(rotate90Degrees(puzzle_straight, 4));
    puzzles.push_back(puzzle_square); // 2. 네모 (회전, 대칭 동일)

    puzzles.push_back(puzzle_ㄱ); // 3. 기역자 (회전, 대칭 모두)
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            puzzle_ㄱ = rotate90Degrees(puzzle_ㄱ, 4);
            puzzles.push_back(puzzle_ㄱ);
        }
        if (i == 0) {
            puzzle_ㄱ = flipHorizontal(rotate90Degrees(puzzle_ㄱ, 4), 4); // 제자리로 회전 후, 대칭
            puzzles.push_back(puzzle_ㄱ);
        } else if (i == 2) {
            puzzle_ㄱ = flipHorizontal(rotate90Degrees(puzzle_ㄱ, 4), 4); // 제자리로 복귀
            puzzle_ㄱ = flipVertical(puzzle_ㄱ, 4);                       // 대칭
            puzzles.push_back(puzzle_ㄱ);
        }
    }

    puzzles.push_back(puzzle_ㄹ); // 4. 리을자 (회전, 대칭 모두)
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            puzzle_ㄹ = rotate90Degrees(puzzle_ㄹ, 4);
            puzzles.push_back(puzzle_ㄹ);
        }
        if (i == 0) {
            puzzle_ㄹ = flipHorizontal(rotate90Degrees(puzzle_ㄹ, 4), 4); // 제자리로 회전 후, 대칭
            puzzles.push_back(puzzle_ㄹ);
        } else if (i == 2) {
            puzzle_ㄹ = flipHorizontal(rotate90Degrees(puzzle_ㄹ, 4), 4); // 제자리로 복귀
            puzzle_ㄹ = flipVertical(puzzle_ㄹ, 4);                       // 대칭
            puzzles.push_back(puzzle_ㄹ);
        }
    }

    puzzles.push_back(puzzle_ㅜ); // ㅜ자 (회전만)
    for (int i = 0; i < 3; ++i) {
        puzzle_ㅜ = rotate90Degrees(puzzle_ㅜ, 4);
        puzzles.push_back(puzzle_ㅜ);
    }

    /*
    1. 인덱스를 잡고 piece와 대치. 안에 있는 점수를 얻고 범위 밖이면 종료
    */

    int max_score = 0;

    for (int cur_y = 0; cur_y < N; ++cur_y) {
        for (int cur_x = 0; cur_x < M; ++cur_x) {
            // 현재 인덱스 = {x, y}
            for (const auto &puzzle : puzzles) { // 검사할 모양
                int cur_score = 0;
                for (const auto &piece : puzzle) {
                    if (cur_x + piece.x < M && cur_y + piece.y < N) { // VALID CHECK
                        cur_score += map[cur_y + piece.y][cur_x + piece.x];
                    } else {
                        cur_score = 0;
                        break; // 경계 밖이라면 다음 퍼즐로 넘기기
                    }
                }
                // 단일 퍼즐 검사 완료
                max_score = max(max_score, cur_score);
            }
        }
    }

    cout << max_score;

    return 0;
}

---

리모컨 (골드 5 - 브루트포스)

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

실수하기 쉬운 단순 브루트포스 문제였다.
0부터 99999까지 탐색해서 풀 수 있는 문제.

// 백준: 리모컨
// https://www.acmicpc.net/problem/1107
// 2024-05-10

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

bool isValidChannel(const string &channel, const vector<int> disabled) {
    for (char c : channel) {
        if (find(disabled.begin(), disabled.end(), c - '0') != disabled.end())
            return false;
    }
    return true;
}

int find_closest_channel(int target, const vector<int> &disabled_buttons) {
    int minPress = abs(target - 100);
    if (disabled_buttons.size() == 10) // 모든 버튼 X
        return minPress;

    for (int num = 0; num <= 999999; num++) {
        string str_num = to_string(num);
        if (isValidChannel(str_num, disabled_buttons)) {
            int pressCount = str_num.length() + abs(num - target);
            minPress = min(minPress, pressCount);
        }
    }

    return minPress;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int target_channel, M;
    vector<int> disabled_buttons;
    cin >> target_channel >> M;
    for (int i = 0; i < M; ++i) {
        int t;
        cin >> t;
        disabled_buttons.push_back(t);
    }

    cout << find_closest_channel(target_channel, disabled_buttons);
    return 0;
}

---

AC (골드 5 - 자료구조, 문자열 파싱)

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

보자마자 deque를 써야한다고 생각이 들었다.
정답이 맞았고, 입력 양식이 까다로워서 파싱만 잘 하면 쉽게 풀 수 있는 문제였다.

// 백준: AC
// https://www.acmicpc.net/problem/5430
// 2024-05-13

#include <deque>
#include <iostream>
#include <sstream>
#include <string>
using namespace std;

deque<int> parseArray(const string &input) {
    deque<int> result;
    string trimmed = input.substr(1, input.size() - 2);
    stringstream ss(trimmed);
    string item;

    while (getline(ss, item, ',')) {
        if (!item.empty()) {
            result.push_back(stoi(item));
        }
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        string p; // 수행할 함수 p
        cin >> p;
        int n; // 배열 수의 개수 n
        cin >> n;
        cin.ignore();
        string input;
        getline(std::cin, input);
        deque<int> dq = parseArray(input);
        int SIZE = p.length();
        bool direction_flag = true;
        bool stop = false;
        for (int i = 0; i < SIZE && !stop; ++i) {
            if (p[i] == 'D') { // 버리기
                if (dq.empty()) {
                    cout << "error\n";
                    stop = true;
                    break;
                } else {
                    if (direction_flag)
                        dq.pop_front();
                    else
                        dq.pop_back();
                }
            } else if (p[i] == 'R') { // 뒤집기
                direction_flag = !direction_flag;
            }
        }

        if (!stop) {
            if (dq.empty()) {
                cout << "[]\n";
            } else {
                string sb = "[";
                while (!dq.empty()) {
                    if (direction_flag) {
                        sb += to_string(dq.front()) + ",";
                        dq.pop_front();
                        // cout << dq.front() << " ";
                        // dq.pop_front();
                    } else {
                        sb += to_string(dq.back()) + ",";
                        dq.pop_back();
                        // cout << dq.back() << " ";
                        // dq.pop_back();
                    }
                }
                sb.pop_back();
                cout << sb + "]\n";
            }
        }
    }
    return 0;
}

---

적록색약 (골드 5 - 그래프 탐색)

RGB 정보가 담긴 맵이 주어질 때, 일반인과 적록색약이 보는 구역의 개수를 출력하는 그래프 문제.
적록색약은 R과 G를 구분하지 못한다. 따라서 적록색약에 대해서는 R과 G를 같다고 두고 두번 탐색했다.

플러드-필 알고리즘과 같다. 모든 칸에 대해 for문을 돌리면서, 아직 방문되지 않았다면 그곳을 기점으로 같은 색을 쭉 방문 체크한다.

'아직 방문되지 않아서 기점이 된 곳의 수' = '구역의 수' 다.

코드가 더럽다. 다음에는 코드가 너무 복잡해지면 탐색 부분을 함수로 빼야겠다.

// 백준: 적록색약
// https://www.acmicpc.net/problem/10026
// 2024-05-14
// 다음부턴 BFS를 함수로 빼자

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<char>> map(N, vector<char>(N));
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            cin >> map[r][c];
        }
    }

    int loop = 2;
    int normal_count = 0;
    int blind_count = 0;
    while (loop--) {
        vector<vector<bool>> visited(N, vector<bool>(N, false));
        queue<pair<int, int>> q; // (r, c)
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                if (!visited[r][c]) { // 방문하지 않았다면
                    if (loop == 1)
                        ++normal_count;
                    else
                        ++blind_count;
                    visited[r][c] = true;
                    char cur_color = map[r][c];
                    q.push({r, c});
                    while (!q.empty()) {
                        int cur_r = q.front().first;
                        int cur_c = q.front().second;
                        q.pop();
                        for (int i = 0; i < 4; ++i) {
                            int next_r = cur_r + dr[i];
                            int next_c = cur_c + dc[i];
                            if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < N && !visited[next_r][next_c]) { // VALID CHECK
                                if (loop == 1) {                                                                      // 일반인 검사
                                    if (map[next_r][next_c] == cur_color) {
                                        q.push({next_r, next_c});
                                        visited[next_r][next_c] = true; // 방문 체크는 큐를 넣을 때 해야 함 (효율성)
                                    }
                                } else if (loop == 0) {                                                 // 적록색약 검사
                                    if (cur_color == 'R' || cur_color == 'G') {                         // 적 or 녹이라면
                                        if (map[next_r][next_c] == 'R' || map[next_r][next_c] == 'G') { // 둘 중 하나여도
                                            q.push({next_r, next_c});
                                            visited[next_r][next_c] = true;
                                        }
                                    } else { // 블루라면
                                        if (map[next_r][next_c] == cur_color) {
                                            q.push({next_r, next_c});
                                            visited[next_r][next_c] = true;
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }

    cout << normal_count << " " << blind_count;
    return 0;
}

---

이중 우선순위 큐 (골드 4 - 우선순위 큐, 자료구조)

이중 우선순위 큐의 구현 아이디어를 알 수 있는 교육적인 문제.
간단하게 priority_queue를 두개 사용해서 구현하면 되는데. 최소 힙/최대 힙에서 .pop() 한거를 서로 알 수 없다는 게 문제다.

이를 해결하기 위해서 숫자의 출현 횟수를 추적했다. unordered_map 으로 insert된 숫자를 추적하고, delete되면 다시 숫자를 빼는 방법으로 추적했고. 각 접근 동작마다 clean 함수로 minHeap이나 maxHeap의 .top() 의 현재 출현 횟수가 0이라면 .pop() 하도록 했다.

이렇게 중간 지점에서는 서로의 값이 다를 수 있어도. 사용할 때마다 동기화하는 방식으로 구현했다.
최소 힙을 구현할 때는 functional 헤더를 include하고 std::greater을 사용함에 유의하자.

// 백준: 이중 우선순위 큐
// https://www.acmicpc.net/problem/7662
// 2024-05-14

#include <functional>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;

/*
1. 최소 힙과 최대 힙을 동시에 운영해야 한다.
2. 최대 힙이나 최소 힙에서 .pop 된건 서로 알 수 없다.
3. 따라서, 숫자의 출현 횟수를 기록해놓고 valid 한지 체크한다.
*/

class DoubleEndedPriorityQueue {
  private:
    priority_queue<int> maxHeap;
    priority_queue<int, vector<int>, greater<int>> minHeap;
    unordered_map<int, int> count; // 출현 횟수

    template <typename T> void clean(T &heap) { // 값 동기화
        while (!heap.empty() && count[heap.top()] == 0) {
            heap.pop();
        }
    }

  public:
    void insert(int value) {
        maxHeap.push(value);
        minHeap.push(value);
        count[value]++;
    }

    void deleteMax() {
        clean(maxHeap);
        if (!maxHeap.empty()) { // 문제 본문: 비어있다면 무시해도 좋다.
            int value = maxHeap.top();
            maxHeap.pop();
            count[value]--;
        }
    }

    void deleteMin() {
        clean(minHeap);
        if (!minHeap.empty()) {
            int value = minHeap.top();
            minHeap.pop();
            count[value]--;
        }
    }

    int getMax() {
        clean(maxHeap);
        // if (!maxHeap.empty())
        return maxHeap.top();
    }

    int getMin() {
        clean(minHeap);
        // if (!minHeap.empty())
        return minHeap.top();
    }

    bool empty() {
        clean(minHeap);
        return minHeap.empty();
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC;
    cin >> TC;

    while (TC--) {
        DoubleEndedPriorityQueue depq;
        int k;
        cin >> k;
        while (k--) {
            char command;
            int n;
            cin >> command >> n;
            if (command == 'I') { // INSERT
                depq.insert(n);
            } else if (command == 'D') { // DELETE
                if (n == 1)              // 최댓값
                    depq.deleteMax();
                else if (n == -1) // 최솟값
                    depq.deleteMin();
            }
        }

        // 출력
        if (depq.empty())
            cout << "EMPTY\n";
        else {
            cout << depq.getMax() << " " << depq.getMin() << "\n";
        }
    }

    return 0;
}

---

정리

이렇게 총 8개의 실버 상위 ~ 골드 하위 문제를 풀었는데. 문제를 풀면서 딱히 어렵거나 막히는 점은 없었던 것 같다.

원래는 실버 문제도 어려워 했는데. 요즘은 골드 하위 문제도 특별한 어려움 없이 푸는 것 같아서 기초가 견고해졌음을 느낀다. 그렇다고 지금 나의 실력에 충족감이 느껴지진 않는다.

골드 상위 ~ 플레 문제도 쓱싹 푸는 날이 오길! 파이팅 ~

끝.