240604: 클래스 4 금장까지 한 보 🔥

2024-06-04

클래스 4 금장까지 한 보.

2주 만에 돌아왔다. 아무것도 안한 것은 아니고, 문제를 열심히 풀었다. 단지 업데이트를 몰아서 할 뿐.
이렇게 약간의 딜레이를 가지고 글을 쓰는 것도 문제를 푼 당일에 바로 올리는 것보다 복습의 효과가 클 것 같다.

해결한 문제들

• 최소비용 구하기 (골드 5 - 1916)
• 내려가기 (골드 5 - 2096)
• 치킨 배달 (골드 5 - 15686)
• 파이프 옮기기 1 (골드 5 - 17070)
• 거짓말 (골드 4 - 1043)
• 알파벳 (골드 4 - 1987)
• 별 찍기 - 11 (골드 4 - 2448)
• 이진 검색 트리 (골드 4 - 5639) 2회차
• 숨바꼭질 2 (골드 4 - 12851)
• 시그마 (골드 4 - 13172)
• 연구소 (골드 4 - 14502)
• 서강그라운드 (골드 4 - 14938)
• 미세먼지 안녕! (골드 4 - 17144)
• 치즈 (골드 3 - 2638)

금장까지 남은 문제들 :

• 최소비용 구하기 2
• 아기 상어

---

중요 이벤트

1. 네이버 부스트캠프에 지원하려고 자기소개서를 쓰고 있다. 특이하게 코딩 테스트의 비중이 그다지 높진 않은 것 같다. 나는 요즘 알고리즘에 불을 태우고 있기에 불리한 요소지만, 자기소개서의 질문 내용을 보니 나랑 커리큘럼이나 가치관이 잘 맞을 것 같다.
2. 이전 게시글에서 모각코를 운영하게 되었다고 했는데. 성공적으로 진행했다. 분위기는 생각보다 편하고 즐거웠다. 서로 존중하며 커뮤니케이션하는 모습이 인상깊었다. 이번주 목요일에도 계획대로 진행 할 예정이다.
3. SSAFY 앰배서더 활동이 끝났다. 정상적으로 수료했다.

---

최소비용 구하기 (골드 5 - 데이크스트라)

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

아주 기본적인 다익스트라 최단거리 문제. priority_queue를 사용해서 최단 거리의 노드 먼저 BFS 탐색하도록 한다.

당연하지만 다익스트라에서는 방문 배열을 사용하면 안된다.

최단 거리 알고리즘은 크게 3가지가 있는데

• 다익스트라 알고리즘
• 벨만-포드 알고리즘
• 플로이드 워셜 알고리즘

다익스트라 알고리즘은 음의 가중치가 없는 그래프에서 (정확하게는, 음의 사이클이 없어야 한다) 사용할 수 있는 single-source shortest path(특정 노드에 대해 모든 각 노드까지의 최단거리)이고, 가장 빠르다.

벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 특정 노드에 대해 모든 각 노드까지의 최단거리를 구하지만 음의 가중치가 있는 경우에서도 사용할 수 있다 (음의 사이클이 발견되는 순간 최단 거리는 의미가 없어지지만, 적어도 음의 사이클을 감지할 수 있다). 다익스트라 알고리즘보다 느리다.

플로이드 워셜 알고리즘은 서로 모든 노드끼리의 최단 거리를 인접 행렬 형식으로 구하는 최단거리 알고리즘이다.

// 백준: 최소 비용 구하기
// https://www.acmicpc.net/problem/1916
// 2024-05-22

/*
다익스트라는 방문 배열(visited)을 사용하면 안된다.
if (cur_weight > dist[cur_node]) 로 처리하자.
*/

#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define INF (~0U >> 2)
using namespace std;

int N, M; // 도시 개수 N, 버스 개수 M

int dijkstra(int start, int dest, vector<vector<pair<int, int>>> &adj) {
    vector<int> dist(N + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 최단 거리 탐색을 위한 우선순위 큐
    dist[start] = 0;                                                                    // 출발 지점
    pq.push({0, start});                                                                // 가중치, 노드

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        int cur_weight = pq.top().first;
        pq.pop();

        if (cur_weight > dist[cur_node])
            continue;

        for (const auto &next : adj[cur_node]) {
            int next_node = next.second;
            int weight = next.first;
            int next_weight = cur_weight + weight;
            if (next_weight < dist[next_node]) {
                dist[next_node] = next_weight;
                pq.push({next_weight, next_node});
            }
        }
    }

    return dist[dest];
}

int main() {
    cin >> N >> M;
    vector<vector<pair<int, int>>> adj(N + 1, vector<pair<int, int>>()); // 가중치, 노드
    for (int i = 0; i < M; ++i) {
        int start_node, end_node, weight;
        cin >> start_node >> end_node >> weight;
        adj[start_node].push_back({weight, end_node});
    }
    int start, dest;
    cin >> start >> dest;

    cout << dijkstra(start, dest, adj);
    return 0;
}

---

내려가기 (골드 5 - 슬라이딩 윈도우, DP)

N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대 점수, 최소 점수를 구하는 프로그램을 작성하시오. 점수는 원룡이가 위치한 곳의 수의 합이다.

이 문제는 점화식을 유추하기 쉬운 DP 문제지만, 메모리 제한이 4MB에 N이 10만으로 메모리를 아끼지 않으면 MLE를 피할 수 없는 문제였다.

Memoization하는 DP 배열을 2차원으로 만들면 편하겠지만, 이 문제에서는 메모리가 넉넉지 않다. 따라서 '슬라이딩 윈도우' 기법을 사용해야 하는데 그냥 단순하게 필요하지 않은 부분을 슬라이딩 해놓고 원하는 범위만 보는 기법? 꼼수? 라고 보면 편할 것 같다.

이 문제에서는 현재의 최적해는 이전 문제의 최적해에서만 영향 받기 때문에 DP 점화식에서는 현재 인덱스의 i-1 부분만 사용할 것이다. 따라서 2차원 배열로 만들어서 모든 정보를 저장할 필요 없이. 그저 이전의 정보만 저장하면 문제를 풀 수 있다.

점화식에서 어차피 안쓰이는 범위의 배열을 생각해보면 최적화 방법을 떠올리는 것은 어렵지 않다. 이러한 최적화 방법을 '토글링' 이라고 한다.

길이가 3인 일차원 배열: max_dp와 min_dp를 선언하고 각각 현재 층의 각 왼쪽 / 중앙 / 오른쪽 요소를 갖도록 한다 매 분기마다 max_dp와 min_dp에 저장되어 있는 값과 입력받은 값을 비교하며 업데이트 해나간다.

// 백준: 내려가기
// https://www.acmicpc.net/problem/2096
// 2024-05-22

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<vector<int>> score(3, vector<int>(N, 0)); // xy 체계
    for (int y = 0; y < N; ++y) {
        for (int x = 0; x < 3; ++x) {
            cin >> score[x][y];
        }
    }

    vector<int> max_dp(3, 0);
    vector<int> min_dp(3, 0);

    for (int i = 0; i < 3; ++i) {
        max_dp[i] = score[i][0];
        min_dp[i] = score[i][0];
    }

    /*
     MLE를 받지 않으려면 dp를 1차원 배열로 해야될 것 같다.

     길이가 3인 일차원 배열: max_dp와 min_dp를 선언하고 각각 현재 층의 각 왼쪽 / 중앙 / 오른쪽 요소를 갖도록 한다
     매 분기마다 max_dp와 min_dp에 저장되어 있는 값과 입력받은 값을 비교하며 업데이트 해나간다.
    */

    for (int y = 1; y < N; ++y) {
        int prev_max[3] = {max_dp[0], max_dp[1], max_dp[2]};
        int prev_min[3] = {min_dp[0], min_dp[1], min_dp[2]};

        max_dp[0] = max(prev_max[0], prev_max[1]) + score[0][y];
        max_dp[1] = max({prev_max[0], prev_max[1], prev_max[2]}) + score[1][y];
        max_dp[2] = max(prev_max[1], prev_max[2]) + score[2][y];

        min_dp[0] = min(prev_min[0], prev_min[1]) + score[0][y];
        min_dp[1] = min({prev_min[0], prev_min[1], prev_min[2]}) + score[1][y];
        min_dp[2] = min(prev_min[1], prev_min[2]) + score[2][y];
    }

    cout << max({max_dp[0], max_dp[1], max_dp[2]}) << " " << min({min_dp[0], min_dp[1], min_dp[2]});
    return 0;
}

---

치킨 배달 (골드 5 - 백트래킹, 브루트포스)

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

이 문제도 별 생각 없이 풀면 TLE가 난다.

백트래킹으로 가능한 치킨 점포 조합을 모두 구하고, 완전탐색(브루트포스) 방식으로 각 조합에 대해서 최단 '치킨 거리' 를 구하는 것 까진 맞는데..

BFS가 아닌 맨해튼 거리로 최단 거리를 구해야 한다. 문제에서 주어지는 격자 도시는 모든 가중치가 똑같은 인접한 그래프이기 때문에, BFS탐색을 사용하지 않아도 단순히 두 좌표간의 차이로 거리를 구할 수 있다 (맨해튼 거리)

BFS를 사용하면 TLE를 받는다.

쉽게 푸는 방법이 있을 줄 알았는데 결국 가장 naive하게 푸는 게 정답이었다.

// 백준: 치킨 배달
// https://www.acmicpc.net/problem/15686
// 2024-05-22

/*
가지치기: 알려진 최솟값보다 높은 값이 갱신되면 중단
*/

#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

int N, M; // N*N 크기의 도시, 폐업시키지 않을 치킨 집 M
vector<vector<pair<int, int>>> paths;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};

void getAllCombination(vector<pair<int, int>> &path, vector<pair<int, int>> &chicken_markets, int start) {
    if (path.size() == M) {
        paths.push_back(path);
        return;
    }

    int SIZE = chicken_markets.size();
    for (int i = start; i < SIZE; ++i) {
        int cur_r = chicken_markets[i].first;
        int cur_c = chicken_markets[i].second;
        path.push_back({cur_r, cur_c});
        getAllCombination(path, chicken_markets, i + 1);
        path.pop_back();
    }
}

// BFS 탐색을 사용했는데, 맨해튼 거리를 사용해서 (절댓값 좌표의 차이) TLE를 막자
// int getNearestChicken(int start_r, int start_c, vector<vector<int>> &map) {
//     vector<vector<bool>> visited(N, vector<bool>(N, false));
//     queue<pair<int, pair<int, int>>> q;
//     q.push({0, {start_r, start_c}});
//     while (!q.empty()) {
//         int cur_r = q.front().second.first;
//         int cur_c = q.front().second.second;
//         int cur_weight = q.front().first;
//         q.pop();

//         if (map[cur_r][cur_c] == 2) { // 치킨집이라면
//             return cur_weight;
//         }

//         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]) {
//                 visited[next_r][next_c] = true;
//                 q.push({cur_weight + 1, {next_r, next_c}});
//             }
//         }
//     }
//     return -1; // 찾지 못함
// }

int getNearestChicken(vector<vector<int>> &map) {
    int known_shortest_dist = (~0U >> 2);
    for (const auto &path : paths) {
        int dist_sum = 0;
        bool stop = false;
        for (int r = 0; r < N && !stop; ++r) {
            for (int c = 0; c < N && !stop; ++c) {
                if (map[r][c] == 1) { // 집이라면
                    int cur_shortest_dist = (~0U >> 2);
                    for (const auto &next : path) {
                        int cur_chicken_r = next.first;
                        int cur_chicken_c = next.second;
                        // |r1 - r2| + |c1 + c2|
                        cur_shortest_dist = min(cur_shortest_dist, abs(r - cur_chicken_r) + abs(c - cur_chicken_c));
                    }
                    dist_sum += cur_shortest_dist;
                    if (dist_sum >= known_shortest_dist) {
                        stop = true;
                        break;
                    }
                }
            }
        }
        if (!stop)
            known_shortest_dist = min(known_shortest_dist, dist_sum);
    }
    return known_shortest_dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    vector<vector<int>> map(N, vector<int>(N));
    vector<pair<int, int>> chicken_markets;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {
            cin >> map[r][c];
            if (map[r][c] == 2) { // 치킨 집 정보 저장
                chicken_markets.push_back({r, c});
                map[r][c] = 0; // 빈칸으로 되돌려놓기
            }
        }
    }

    vector<pair<int, int>> path;
    getAllCombination(path, chicken_markets, 0);
    cout << getNearestChicken(map);
    return 0;
}

---

파이프 옮기기 (골드 5 - 그래프 이론, DP)

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다.
가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

태그는 다이나믹 프로그래밍과 그래프 이론이지만, 나는 그냥 재귀 완전탐색으로 풀었다.
아마 DP로만 풀리는 문제는 플래쪽에 있는 것 같다.

그리고 사실상 재귀 완전탐색이 DFS와 유사하기도 하고..
문제가 복잡해보이지만 시간 제한이 널널하기에 그냥 naive하게 풀면 풀리는 문제였다.

확실히 요즘 문제 풀 때 느끼는데, 푸는 센스가 늘은 것 같다. 실력이 늘었다고 봐야겠지 ~

// 백준: 파이프 옮기기 1
// https://www.acmicpc.net/problem/17070
// 2024-05-23

/*
시뮬레이션 문제인 것 같다.
*/

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

int N; // N*N 크기의 맵
vector<vector<int>> map;
int cnt = 0;

// 이전 파이프가 가로로 놓여있을 때 다음 파이프의 가능한 위치
int horizontal_dr[2] = {0, 1};
int horizontal_dc[2] = {1, 1};
// 이전 파이프가 세로로 놓여있을 때
int vertical_dr[2] = {1, 1};
int vertical_dc[2] = {0, 1};
// 이전 파이프가 대각선으로 놓여있을 때
int diagonal_dr[3] = {0, 1, 1};
int diagonal_dc[3] = {1, 0, 1};

int getPipeDirection(int &start_r, int &start_c, int &end_r, int &end_c) { // 가로: -1, 세로: 1, 대각선: 0
    if (start_r == end_r && end_c - start_c == 1)                          // 가로
        return -1;
    else if (start_c == end_c && end_r - start_r == 1) // 세로
        return 1;
    else
        return 0;
}

void solution(int start_r, int start_c, int end_r, int end_c) {
    // 현재 파이프의 방향 알아내기
    int cur_direction = getPipeDirection(start_r, start_c, end_r, end_c);

    if (cur_direction == 0 && (map[end_r - 1][end_c] == 1 || map[end_r][end_c - 1] == 1)) // 대각선 벽지 긁었다면 종료
        return;

    if (end_r == N && end_c == N) { // 목표 지점 도착하면 카운트 증가하고 종료
        ++cnt;
        return;
    }

    // 가로
    if (cur_direction == -1) {
        for (int i = 0; i < 2; ++i) {
            int next_end_r = end_r + horizontal_dr[i];
            int next_end_c = end_c + horizontal_dc[i];
            if (next_end_r <= N && next_end_c <= N && map[next_end_r][next_end_c] == 0) { // VALID CHECK
                solution(end_r, end_c, next_end_r, next_end_c);
            }
        }
    }

    // 세로
    else if (cur_direction == 1) {
        for (int i = 0; i < 2; ++i) {
            int next_end_r = end_r + vertical_dr[i];
            int next_end_c = end_c + vertical_dc[i];
            if (next_end_r <= N && next_end_c <= N && map[next_end_r][next_end_c] == 0) { // VALID CHECK
                solution(end_r, end_c, next_end_r, next_end_c);
            }
        }
    }

    // 대각선
    else if (cur_direction == 0) {
        for (int i = 0; i < 3; ++i) {
            int next_end_r = end_r + diagonal_dr[i];
            int next_end_c = end_c + diagonal_dc[i];
            if (next_end_r <= N && next_end_c <= N && map[next_end_r][next_end_c] == 0) {
                solution(end_r, end_c, next_end_r, next_end_c);
            }
        }
    }

    return;
}

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

    solution(1, 1, 1, 2);
    cout << cnt;
    return 0;
}

---

거짓말 (골드 4 - 분리 집합, 그래프 이론)

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

문제를 읽고 그래프 탐색으로 풀 수 있을 것 같다는 생각을 했다. 각 사람들을 노드로 두고, 같은 파티에 참여하는 사람들끼리 간선을 모두 이으면.

"진실을 알고 있는 사람과 간선이 연결되어 있다면. 어떻게든 진실을 알 수 있는 사람이다." 라고 생각했다.
따라서 진실을 알고 있는 사람과 간선이 연결되어 있지 않은 사람들끼리만 이루어져있는 파티에서만 과장을 할 수 있다.

그리고 naive한 아이디어에서 한 단계 더 나아갔다.
분리 집합과 유사한 것 같아서 Union-find를 사용하는 문제라고 확신했다.

분리 집합에 대한 이해가 부족했는데 이를 연습할 수 있는 문제였다. 높은 트리에 낮은 트리를 붙여야 트리가 너무 깊어지는 것을 막을 수 있다.

// 백준: 거짓말
// 2024-05-23
// https://www.acmicpc.net/problem/1043

/*
그래프 탐색 같다.
각 사람들을 노드로 두고, 같은 파티에 참여하는 사람끼리 간선을 잇는다.
진실을 알고 있는 사람과 간선이 연결되어 있다면. 어떻게든 진실을 알 수 있는 사람이다.
따라서 진실을 알고 있는 사람과 간선이 연결되어 있지 않은 사람들끼리만 이루어져있는 파티에서만 과장을 할 수 있다.

근데 문제는 간선 정보 추가할 때 파티에 참가한 사람 모두를 엮어야 되는데 이게 너무 비효율적이다.
Union-find를 사용해야 할 것 같다.

PS. Union-find를 연습할 수 있는 교육적인 문제. 높은 트리에 낮은 트리를 붙여야 트리가 너무 깊어지는 것을 막을 수 있다.
*/

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

vector<int> parents;
vector<int> node_rank;

// union-find
int find_root(int x) {
    if (parents[x] != x)
        parents[x] = find_root(parents[x]);
    return parents[x];
}

void union_root(int x, int y) {
    x = find_root(x);
    y = find_root(y);

    if (x != y) {
        if (node_rank[x] < node_rank[y])
            parents[x] = y;
        else if (node_rank[x] > node_rank[y])
            parents[y] = x;
        else {
            parents[y] = x;
            node_rank[x]++;
        }
    }
}

int main() {
    int N, M; // 사람의 수 N, 파티의 수 M
    cin >> N >> M;

    int truthNum; // 진실을 아는 사람의 수
    cin >> truthNum;
    vector<int> truthPeople(truthNum);
    for (int i = 0; i < truthNum; ++i) {
        cin >> truthPeople[i];
    }

    parents.assign(N + 1, 0);
    node_rank.assign(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        parents[i] = i;
    }

    // 파티 입력받기
    vector<vector<int>> parties(M);
    for (int i = 0; i < M; ++i) {
        int partyNum; // 파티에 오는 사람들
        cin >> partyNum;
        parties[i].resize(partyNum);
        for (int j = 0; j < partyNum; ++j) {
            cin >> parties[i][j];
        }

        // 파티 참석자 모두 union_root
        for (int j = 1; j < partyNum; ++j) {
            union_root(parties[i][0], parties[i][j]);
        }
    }

    // 진실을 아는 사람의 루트 알아내기
    int truthRoot = -1;
    if (truthNum > 0) {
        truthRoot = find_root(truthPeople[0]);
        for (int i = 1; i < truthNum; ++i) {
            union_root(truthPeople[0], truthPeople[i]);
        }
        truthRoot = find_root(truthPeople[0]);
    }

    // 모든 파티를 순회하면서 진실을 아는 사람과 root가 같은 참석자가 없는지 체크
    int cnt = 0;
    for (const auto &party : parties) {
        bool flag = true;
        for (const auto &person : party) {
            if (find_root(person) == truthRoot) { // 진실을 아는 사람과 루트가 같다면
                flag = false;
                break;
            }
        }
        if (flag)
            cnt++;
    }

    cout << cnt;
    return 0;
}

---

알파벳 (백트래킹, 그래프 이론)

세로 
R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 1행 1열 에는 말이 놓여 있다.

말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.

좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.

간단하다. 그냥 그래프 탐색 + 백트래킹 문제인데, 이미 밟은 알파벳을 밟으면 안되니까 체크하면서 가면 된다.
근데 문제는 이미 밟은 알파벳을 배열에 char형태로 담거나 unordered_set 같은걸로 담으면 TLE가 난다. set이 생각보다 해쉬 함수 과정에서 오버헤드가 많이 나는 것 같다. 약간의 속도 차이가 누적되어서 큰 차이를 만든다.

알파벳의 개수는 26개이기 때문에 bool 형태의 vector index에 할당해서 방문을 체크하거나, 비트 마스킹을 사용해서 효율적으로 처리할 수 있다.

나는 비트마스킹을 이용해서 처리했다.
비트마스킹의 기초를 다지게 된 교육적인 문제다.

// 백준: 알파벳
// https://www.acmicpc.net/problem/1987
// 2024-05-23

/*
전형적인 백트래킹 + DFS 문제에
unique 알파벳을 저장하는데에 제일 효율적인 unordered_set으로 알파벳 체크 + 방문체크
방문 체크 배열을 따로 만들 필요가 없다. 어차피 이미 방문한 위치의 경우 알파벳이 겹쳐서 재방문하지 못한다.
unordered_set으로 알파벳을 관리해도 TLE가 난다. 비트마스킹을 해야 한다. 32비트 정수형에서 저장할 수 있는 상태는 총 32개.
대소문자 알파벳의 개수는 26개이기 때문에 충분히 가능하다.

PS. 비트마스킹의 기초를 다지게 된 교육적인 문제.
*/

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

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

int R, C; // R*C의 보드
vector<vector<char>> map;

int known_farthest_depth = 0;

void solution(int depth, int cur_r, int cur_c, int bitmask) {
    if (known_farthest_depth < depth)
        known_farthest_depth = depth;

    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 < R && next_c < C) { // VALID CHECK
            int next_char_bit = 1 << (map[next_r][next_c] - 'A');
            if ((bitmask & next_char_bit) == 0) { // 아직 나오지 않은 알파벳
                solution(depth + 1, next_r, next_c, bitmask | next_char_bit);
                // bitmask &= ~next_char_bit; 재귀 호출 인자에서 값을 변경해서 보내기에, 백트래킹 필요 없음.
            }
        }
    }
}

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

    // unordered_set<char> set;
    int start_bitmask = 1 << (map[0][0] - 'A');
    // set.insert(map[0][0]); // 시작 지점 추가
    solution(1, 0, 0, start_bitmask);
    cout << known_farthest_depth;
    return 0;
}

---

별 찍기 - 11 (골드 4 - 재귀)

예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 라는 간단 명료한 문제지만
재귀 분할정복을 이용해서 풀어야 하는 상당히 머리 아픈 문제.
겁을 먹지 않고 패턴을 찾아서 접근하면 풀 수 있다.. 하지만 처음엔 어떻게 접근해야 할지 감도 잡지 못했다.

일단 공백으로 가득 찬 2차원 배열을 만들고 천천히 채워 나간다는 발상을 하고나서는 마음이 그나마 편안해졌다.

                       *                        
                      * *                       
                     *****                      
                    *     *                     
                   * *   * *                    
                  ***** *****                   
                 *           *                  
                * *         * *                 
               *****       *****                
              *     *     *     *               
             * *   * *   * *   * *              
            ***** ***** ***** *****             
           *                       *            
          * *                     * *           
         *****                   *****          
        *     *                 *     *         
       * *   * *               * *   * *        
      ***** *****             ***** *****       
     *           *           *           *      
    * *         * *         * *         * *     
   *****       *****       *****       *****    
  *     *     *     *     *     *     *     *   
 * *   * *   * *   * *   * *   * *   * *   * *  
***** ***** ***** ***** ***** ***** ***** *****

별을 이런 식으로 채워야 하는데 어떻게 겁을 안 먹을 수가 있을까?

1. 제일 기본 형태를 생각해보자
   N은 항상 3x2^k 수이기 때문에 3x2^0인 3이 N이 될 수 있는 최소의 수이다.
   따라서 제일 기본 형태는 다음과 같고: 이를 그리는 함수를 만들었다.

   *                        
   * *                       

---

```cpp
void draw(int r, int c) {
    output[r][c] = '*';
    output[r + 1][c - 1] = '*';
    output[r + 1][c + 1] = '*';
    output[r + 2][c - 2] = '*';
    output[r + 2][c - 1] = '*';
    output[r + 2][c] = '*';
    output[r + 2][c + 1] = '*';
    output[r + 2][c + 2] = '*';
}

개노가다

2. 이제 전체 배열의 좌표를 받고, 기준에 맞게 분할한다.
   위 기본 형태의 삼각형이 나올때는 N == 3 이 됐을때 뿐이다. 따라서 재귀 함수의 기저 조건으로 N == 3일때 위의 기본 삼각형을 그리도록 한다.

잘 보면 문제에서 주어진 패턴은 모두 기본 삼각형으로만 이루어져 있다. 따라서 적절한 기준으로 배열을 분할하고 적절한 좌표로 draw 함수를 호출해주기만 하면 완성이다.

void solution(int len, int r, int c) {
    if (len == 3) {
        draw(r, c);
        return;
    }

    solution(len / 2, r, c);                     // 윗 부분
    solution(len / 2, r + len / 2, c - len / 2); // 왼쪽 부분
    solution(len / 2, r + len / 2, c + len / 2); // 오른쪽 부분
}

코드는 쉽지만 도출 과정이 결코 쉽지 않다.
비쥬얼적 공포를 선사하는 문제. 좌표 관리가 너무 헷갈린다.

// 백준: 별 찍기 - 11
// 2024-05-23
// https://www.acmicpc.net/problem/2448

/*
Divide and Conquer
으아아아아아악

빈 벡터 공간을 공백으로 채워놓고 그리자는 생각을 하기 전까진, 접근 하기도 힘들었다.
*/

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

void draw(int r, int c) {
    output[r][c] = '*';
    output[r + 1][c - 1] = '*';
    output[r + 1][c + 1] = '*';
    output[r + 2][c - 2] = '*';
    output[r + 2][c - 1] = '*';
    output[r + 2][c] = '*';
    output[r + 2][c + 1] = '*';
    output[r + 2][c + 2] = '*';
}

void solution(int len, int r, int c) {
    if (len == 3) {
        draw(r, c);
        return;
    }

    solution(len / 2, r, c);                     // 윗 부분
    solution(len / 2, r + len / 2, c - len / 2); // 왼쪽 부분
    solution(len / 2, r + len / 2, c + len / 2); // 오른쪽 부분
}

int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(nullptr);
    int N;
    cin >> N;
    output.assign(N, vector<char>(N * 2 - 1, ' '));

    solution(N, 0, N - 1);

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N * 2 - 1; ++c) {
            cout << output[r][c];
        }
        cout << "\n";
    }

    return 0;
}

---

이진 검색 트리 (골드 4 - 트리)

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 아래의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

어떻게 접근해야 할지 감이 안잡혔던 문제. 결국에 트리의 삽입 메서드에 대해 배웠고. 이를 이용해서 풀었다.
이진 검색 트리의 특성은 문제에서 알려준 것과 같이:

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

이다. 따라서 트리의 insert(삽입) 메서드는 위와 같은 규칙으로 자신의 자리를 찾아 나가게 재귀적으로 구현할 수 있다.

먼저, TreeNode 구조체를 만든다. 노드 구조체는 가장 기본적인 value와, 자신의 왼쪽 자식과 오른쪽 자식의 메모리 주소를 가리키고 있다.

struct TreeNode {
    int value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

insert 메서드에서는 재귀적으로 현재 루트의 값과 삽입 값을 비교한다.
만약 루트가 없다면(null) 새로운 TreeNode를 선언해서 root -> 의 왼쪽이나 오른쪽에 넣는다.

이진 트리의 삽입 메서드를 구현해 본 교육적인 문제.

TreeNode *insert(TreeNode *root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }

    if (value > root->value) {
        root->right = insert(root->right, value);
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    }

    return root;
}

전위 순회는: 루트 -> 왼쪽 -> 오른쪽 순의 탐색이기 때문에 문제에서 주어지는 전위 순회 결과의 첫번째는 루트 노드이다. 따라서, 처음 입력되는 값을 루트로 두고 다른 값들을 루트에 모두 insert하면 재귀적으로 이진 검색 트리를 채우게 된다.

이렇게 완성된 트리를 후위 순회: 왼쪽 -> 오른쪽 -> 루트로 재귀적 출력하면 된다.

// 백준: 이진 검색 트리
// https://www.acmicpc.net/problem/5639
// 2024-05-28
// 복습 - 2회차

#include <iostream>
using namespace std;

struct TreeNode {
    int value;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
};

TreeNode *insert(TreeNode *root, int value) {
    if (root == nullptr) {
        return new TreeNode(value);
    }

    if (value > root->value) {
        root->right = insert(root->right, value);
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    }

    return root;
}

void postOrder(TreeNode *root) {
    if (root == nullptr)
        return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->value << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int value;
    cin >> value;
    TreeNode *root = new TreeNode(value);
    while (cin >> value) {
        insert(root, value);
    }
    postOrder(root);
    return 0;
}

---

숨바꼭질 2 (골드 4 - 그래프 탐색)

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.

간단한 BFS 탐색 문제이지만 (최단 경로 문제는 일반적으로 BFS를 사용하는 게 유리하다. BFS 특성상 제일 먼저 도달하는 노드가 자연스럽게 최단 거리이기 때문) 최단 거리 방법의 수도 구해야 하기 때문에 최단 거리 정보를 기록하고 그걸 방문 배열처럼 써서 풀었다. 생각보다 접근법이 어렵진 않았다.

방문 체크를 visited bool 배열로 하면 최단시간 방법의 수를 알 수 없다. 최단 거리를 탐색하고 나면 바로 탐색이 종료되기 때문이다.

그렇다고 방문 체크를 하지 않으면 TLE가 난다. 따라서 dist 배열을 만들어서 방문 체크처럼 사용했다. 같은 수에 대해서 가중치가 더 낮은 것만 통과 시켰다.

// 백준: 숨바꼭질 2
// https://www.acmicpc.net/problem/12851
// 2024-05-28

/*
문제점: 방문 체크를 하면 최단 시간 방법의 수를 얻을 수 없다.
그렇다고 방문 체크를 안하면 TLE가 난다
dist 배열을 만들어서 방문 체크처럼 쓰는 건 어떨까? 같은 수에 대해서 가중치가 더 낮은 것만 통과 시키는 것.
같은 수에 도달하는데에 어떤 루트는 더 높은 가중치를 썼다면 그것은 최단 루트가 아님이 명백하다.
*/

#include <algorithm>
#include <iostream>
#include <iterator>
#include <queue>
#include <utility>
#define INF (~0U >> 2)
using namespace std;

int known_shortest_time = INF;
int shortest_time_count = 0;

void bfs(int N, int K) {
    // bool visited[140001] = {
    //     false,
    // };

    int dist[140001];
    fill(begin(dist), end(dist), INF);

    queue<pair<int, int>> q; // time, pos
    // visited[N] = true;       // 시작 지점 방문 표시
    dist[N] = 0;
    q.push({0, N});

    while (!q.empty()) {
        int cur_pos = q.front().second;
        int cur_time = q.front().first;
        q.pop();

        if (cur_pos == K) { // 목표 도달
            if (known_shortest_time == INF) {
                known_shortest_time = cur_time; // 첫 도달 시간이 무조건 가능 최단 시간
            }

            if (cur_time > known_shortest_time)
                return; // 최단 시간보다 긴 시간이 발견되면 종료
            shortest_time_count++;
        }

        if (cur_time > dist[cur_pos]) // 현재 노드까지 도달한 경로가 최적 경로가 아닌 경우
            continue;

        // dist[cur_pos] = cur_time;

        /*
        그리디적으로 봤을 때 0~10만 범위 밖에서 한 칸 가는 건 완전히 비효율적이므로 해가 될 가능성이 없다
        6만에서 *2를 해서 나머지를 마이너스로 채우는 전략은 유효할 수 있다. 따라서, 곱하기에 대해서는 방문 배열을 넉넉하게 14만까지 허용.
        */

        // movement: +, -
        if (cur_pos + 1 <= 100000 && cur_time + 1 <= dist[cur_pos + 1]) { // 경계 체크, 시간 체크(방문 겸용)
            q.push({cur_time + 1, cur_pos + 1});
            dist[cur_pos + 1] = cur_time + 1;
        }
        if (cur_pos - 1 >= 0 && cur_time + 1 <= dist[cur_pos - 1]) {
            q.push({cur_time + 1, cur_pos - 1});
            dist[cur_pos - 1] = cur_time + 1;
        }

        // movement: 2*X
        if (2 * cur_pos <= 140000 && cur_time + 1 <= dist[2 * cur_pos]) {
            q.push({cur_time + 1, 2 * cur_pos});
            dist[2 * cur_pos] = cur_time + 1;
        }
    }
}

int main() {
    int N, K; // 수빈이 위치 N, 동생 위치 K
    cin >> N >> K;
    bfs(N, K);
    cout << known_shortest_time << "\n" << shortest_time_count;
    return 0;
}

---

Σ (골드 4 - 페르마의 소정리, 모듈러 곱셈 역원)

거의 비문학 지문급의 문제 본문

수학의 장벽은 일단 차치하고, 문제에서 설명하는 것을 요약하자면

1. 각 주사위 기댓값을 분수로 나타낼 수 있다.
2. 기댓값의 합을 구하는데, 통분을 하면서 계산이 너무 복잡해지고 분모가 너무 커진다
3. 따라서 기댓값을 모듈로로 나타낸다
4. 각 주사위에 대한 기댓값을 유클리드 호제법으로 기약분수로 나타낸다
5. 페르마의 소정리를 이용한다

결론적으로 문제를 풀어보면

기약분수 a/b 는 a * <b역원> mod X로 풀고
b의 역원은 (b^X-2) mod X 이다. (왜인지는 이해하려고 하지 말자 .. 아직까진)

따라서 문제에서 원하는 식은.. a * ((b^X-2)%X) 이다.
이걸 모든 주사위에 대해 계산해서 합하면 되는 문제.

코드는 쉽지만, 문제에서 설명하는 개념들이 너무 어려웠다.
그래도 중간에 이해 안되는 부분은 건너뛰고 식 부분만 확인하면 결국엔 풀 수 있었다.

gcd는 GCD(a, b) = GCD(b, r)과 같다는 유클리드 호제법을 이용해서 구현했고, 거듭제곱은 분할정복을 이용해서 구현했다.

gcd와 pow 구현은 조금 더 연습해야겠다. (사실 지금은 50%의 이해와 50%의 익숙함(암기)로 이루어진 느낌)

// 백준: Σ
// https://www.acmicpc.net/problem/13172
// 2024-05-29

/*
페르마의 소정리를 지금 이해하려고 하지 말자.
결론:
1. 기약 분수 만들기 (유클리드 호제법)
2. 모듈러 역원 구하기: a*((b^x-2)%x)
*/

#include <iostream>
#include <vector>
using namespace std;
typedef unsigned long long ll;
#define X 1'000'000'007

/* 중요 !!
GCD(a, b) = A와 B의 최대공약수
r = a mod b 일때
GCD(a, b) = GCD(b, r) 이다.
*/
ll gcd(ll a, ll b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

ll my_pow(ll base, ll exp) {
    ll result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % X;
        }
        base = (base * base) % X;
        exp /= 2;
    }
    return result;
}

int main() {
    int M; // 주사위의 수
    cin >> M;
    ll answer = 0;
    while (M--) {
        ll N, S; // N면체 주사위, 각 눈의 합 S
        cin >> N >> S;
        ll g = gcd(N, S); // 기약분수화
        N /= g;           // 분모 b
        S /= g;           // 분자 a
        // a * (b^X-2)%X
        answer += S * my_pow(N, X - 2) % X;
        answer %= X;
    }
    cout << answer;
    return 0;
}

---

연구소 (골드 4 - 그래프 탐색, 브루트포스)

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

간단한 BFS + 완전탐색(브루트포스) 문제였다. 가능한 벽 조합을 3중 포문으로 모두 순회하도록 하고. 벽이 세워졌을때마다 BFS로 탐색을 돌리면서 안정 영역 크기가 최대가 되는 조합을 찾았다. 덤으로 최적해를 이미 넘어섰다면 가지치기까지..

쉬운 문제였다.

// 백준: 연구소
// https://www.acmicpc.net/problem/14502
// 2024-05-29

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M;         // 맵 사이즈
int wall_cnt = 0; // 벽 개수
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
int known_least_virus_cnt = (~0U >> 2);

void virus_simulation(vector<vector<int>> &map, vector<pair<int, int>> &virus_pos) {
    vector<vector<bool>> visited(N, vector<bool>(M, false));
    int virus_cnt = 0;
    for (const auto &pos : virus_pos) {
        // 바이러스 위치
        int r = pos.first;
        int c = pos.second;

        queue<pair<int, int>> q;
        q.push({r, c});
        visited[r][c] = true;
        while (!q.empty()) {
            // 전파
            int cur_r = q.front().first;
            int cur_c = q.front().second;
            q.pop();

            virus_cnt++;

            if (virus_cnt > known_least_virus_cnt) // 이전 최적해를 이미 넘어섰다면 (가지치기)
                return;

            for (int i = 0; i < 4; ++i) {
                int next_r = cur_r + dr[i];
                int next_c = cur_c + dc[i];
                // VALID CHECK : 경계, 빈칸에만 전파 허용
                if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < M && !visited[next_r][next_c] && map[next_r][next_c] == 0) {
                    q.push({next_r, next_c});
                    visited[next_r][next_c] = true;
                }
            }
        }
    }

    if (virus_cnt < known_least_virus_cnt) // 최솟값 갱신
        known_least_virus_cnt = virus_cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> M;
    // 0: 빈칸
    // 1: 벽
    // 2: 바이러스
    vector<vector<int>> map(N, vector<int>(M));
    vector<pair<int, int>> virus_pos;
    vector<pair<int, int>> possible_place;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> map[r][c];
            if (map[r][c] == 1)
                wall_cnt++; // 최적화를 위해 벽 개수 세놓기
            else if (map[r][c] == 2)
                virus_pos.push_back({r, c});
            else if (map[r][c] == 0)
                possible_place.push_back({r, c});
        }
    }

    // 조합 완전 탐색
    int SIZE = possible_place.size();
    for (int i = 0; i < SIZE; ++i) {
        for (int j = i + 1; j < SIZE; ++j) {
            for (int k = j + 1; k < SIZE; ++k) {
                // 맵 수정
                map[possible_place[i].first][possible_place[i].second] = 1;
                map[possible_place[j].first][possible_place[j].second] = 1;
                map[possible_place[k].first][possible_place[k].second] = 1;

                virus_simulation(map, virus_pos);

                // 맵 수정
                map[possible_place[i].first][possible_place[i].second] = 0;
                map[possible_place[j].first][possible_place[j].second] = 0;
                map[possible_place[k].first][possible_place[k].second] = 0;
            }
        }
    }

    cout << N * M - known_least_virus_cnt - wall_cnt - 3;
    return 0;
}

---

서강그라운드 (골드 4 - 데이크스트라)

예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 하는 게임이다. 서강그라운드에서 1등을 하면 보상으로 치킨을 주는데, 예은이는 단 한번도 치킨을 먹을 수가 없었다. 자신이 치킨을 못 먹는 이유는 실력 때문이 아니라 아이템 운이 없어서라고 생각한 예은이는 낙하산에서 떨어질 때 각 지역에 아이템 들이 몇 개 있는지 알려주는 프로그램을 개발을 하였지만 어디로 낙하해야 자신의 수색 범위 내에서 가장 많은 아이템을 얻을 수 있는지 알 수 없었다.

각 지역은 일정한 길이 l (1 ≤ l ≤ 15)의 길로 다른 지역과 연결되어 있고 이 길은 양방향 통행이 가능하다. 예은이는 낙하한 지역을 중심으로 거리가 수색 범위 m (1 ≤ m ≤ 15) 이내의 모든 지역의 아이템을 습득 가능하다고 할 때, 예은이가 얻을 수 있는 아이템의 최대 개수를 알려주자.

이 문제도 꽤나 쉽게 풀었다. 간단한 다익스트라 문제였다. 그냥 naive하게 모든 노드에 대해 다익스트라 탐색을 하고 dist <= 15인 아이템 합의 최대 개수를 구했다.

그래프 탐색 문제는 아무래도 정형적인 문제가 많다 보니까 쉽게 느껴지는 것 같다. 그래프를 밥먹듯이 풀어봤어서 그런가.. 이젠 실버 ~ 골드 하위 수준의 그래프 문제는 마스터 한 것 같다.

// 백준: 서강그라운드
// https://www.acmicpc.net/problem/14938
// 2024-05-31

/*
모든 노드에 대해서 다익스트라를 하고, 거리가 15 이내인 아이템 값 합
*/

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#define INF (~0U >> 2)
using namespace std;

int n, m, r; // 지역의 개수 n, 예은이의 수색 범위 m, 길의 개수 r
vector<int> dijkstra(int start, vector<vector<pair<int, int>>> &adj) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    vector<int> dist(n + 1, INF);
    dist[start] = 0; // 시작 지점 0으로
    pq.push({0, start});

    while (!pq.empty()) {
        int cur_node = pq.top().second;
        int cur_weight = pq.top().first;
        pq.pop();

        if (cur_weight > dist[cur_node])
            continue; // 알려진 최단 거리보다 길면 스킵

        for (const auto &next : adj[cur_node]) {
            int next_node = next.second;
            int weight = next.first;
            int new_weight = cur_weight + weight;
            if (new_weight < dist[next_node]) {
                dist[next_node] = new_weight;
                pq.push({new_weight, next_node});
            }
        }
    }

    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> r;              // 지역의 개수 n, 예은이의 수색 범위 m, 길의 개수 r
    vector<int> item_info(n + 1, 0); // 노드별 아이템 개수 정보
    for (int i = 1; i <= n; ++i) {
        cin >> item_info[i];
    }

    vector<vector<pair<int, int>>> adj(n + 1, vector<pair<int, int>>()); // 가중치, 노드
    for (int i = 0; i < r; ++i) {                                        // 간선 입력받기
        int from, to, weight;
        cin >> from >> to >> weight;
        adj[from].push_back({weight, to});
        adj[to].push_back({weight, from});
    }

    // 각 노드에 대해서 다익스트라 탐색, 가중치가 m 이하인 모든 지역의 아이템 수 합 얻기
    int max_sum = 0;
    for (int cur_node = 1; cur_node <= n; ++cur_node) {
        vector<int> dist = dijkstra(cur_node, adj);
        int item_sum = 0;                             // 얻을 수 있는 아이템 합계
        for (int target = 1; target <= n; ++target) { // cur_node로부터 거리가 m 이하인 노드 탐색
            if (dist[target] <= m) {                  // 거리가 m 이내라면
                item_sum += item_info[target];
            }
        }
        max_sum = max(max_sum, item_sum);
    }

    cout << max_sum;
    return 0;
}

---

미세먼지 안녕! (골드 4 - 시뮬레이션, 구현)

미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)에 있는 미세먼지의 양을 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다.

공기청정기는 항상 1번 열에 설치되어 있고, 크기는 두 행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 있고, (r, c)에 있는 미세먼지의 양은 Ar,c이다.

1초 동안 아래 적힌 일이 순서대로 일어난다.

미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.
(r, c)에 있는 미세먼지는 인접한 네 방향으로 확산된다.
인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
확산되는 양은 Ar,c/5이고 소수점은 버린다. 즉, ⌊Ar,c/5⌋이다.
(r, c)에 남은 미세먼지의 양은 Ar,c - ⌊Ar,c/5⌋×(확산된 방향의 개수) 이다.
공기청정기가 작동한다.
공기청정기에서는 바람이 나온다.
위쪽 공기청정기의 바람은 반시계방향으로 순환하고, 아래쪽 공기청정기의 바람은 시계방향으로 순환한다.
바람이 불면 미세먼지가 바람의 방향대로 모두 한 칸씩 이동한다.
공기청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기청정기로 들어간 미세먼지는 모두 정화된다.

방의 정보가 주어졌을 때, T초가 지난 후 구사과의 방에 남아있는 미세먼지의 양을 구해보자.

 

재밌어 보이는 구현 / 시뮬레이션 문제였다. 딱히 구현 아이디어가 어렵지 않고 시간만 조금 필요한 정도 난이도의 문제였다. 먼지의 확산은 BFS로 구현하고, 바람도 매 노드에서 다음 바람 방향을 결정하는 식으로 구현했다.

주의할 점이 있다면 미세먼지의 확산이 '동시에' 일어난다는 것이다. 순차적으로 처리했다간 이전 공간에서의 확산이 다음 확산에 영향을 미칠 수 있다. 따라서 확산 정보를 바로 연산중인 맵에 업데이트 하지 않고, 정보를 담아놨다가 모든 확산 시뮬레이션이 끝나고 원본 맵에 업데이트 하는 것이 바람직하다.

solved.ac 기여 한마디: 공기청정기 순환 부분 로직과 확산이 '동시'에 일어난다는 점만 유의하면 쉬운 문제입니다. 만약 시간 제한이 있다면 힘들었겠지만 느긋하게 구현했습니다.

// 백준: 미세먼지 안녕!
// https://www.acmicpc.net/problem/17144
// 2024-06-02
// 재밌어 보이는 시뮬레이션 구현 문제!

/* 1초에 일어나는 일
1. 미세먼지가 확산된다.
2. 공기청정기가 작동한다.

공기청정기는 항상 1번 열에 설치되어 있다.


인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산이 일어나지 않는다.
확산되는 양은 A/5이고 소수점은 버린다. 즉, ⌊A/5⌋이다.
(r, c)에 남은 미세먼지의 양은 A - ⌊A/5⌋×(확산된 방향의 개수) 이다.

주의사항: 확산은 동시에 일어나고, 확산 이전에 있었던 미세먼지에 대해서만 일어나고, 순서에 영향을 받지 않는다 (원본 맵에서 일어난다음, 가중치를 합한다)

공기청정기 작동:  공기 청정기에서는 바람이 나온다. 위쪽 공기청정기의 바람은 반시계 방향 순환, 아래쪽은 시계 방향으로 순환한다.
바람이 불면 미세먼지는 바람의 방향대로 모두 한칸씩 이동한다. 공기 청정기에서 부는 바람은 미세먼지가 없는 바람이고, 공기 청정기로 들어간 바람은 모두 정화된다.
*/

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

int R, C, T; // R*C 맵, T초 후 미세먼지 양
vector<vector<int>> map;

int dr[4] = {1, -1, 0, 0}; // 인접 탐색 배열
int dc[4] = {0, 0, 1, -1};

pair<int, int> conditioner_upper_pos = make_pair(-1, -1); // 공기 청정기 위쪽 좌표
pair<int, int> conditioner_below_pos;

pair<int, int> getNextPos(int cur_r, int cur_c, bool clockDir) { // 다음 바람 방향을 구하는 함수
    // clockDir ? 시계 : 반시계
    if (clockDir) {
        if (cur_r != 1 && cur_c != 1 && cur_r != R && cur_c != C) // 그 어느 모서리도 아니라면
            return make_pair(cur_r, cur_c + 1);                   // 오른쪽으로
        if (cur_c == C && cur_r != R)                             // 오른쪽 끝이지만, 모서리는 아니라면
            return make_pair(cur_r + 1, cur_c);                   // 아래로
        if (cur_r == R && cur_c != 1)                             // 아래쪽 끝이지만, 모서리는 아니라면
            return make_pair(cur_r, cur_c - 1);                   // 왼쪽으로
        else                                                      // 왼쪽 끝이라면
            return make_pair(cur_r - 1, cur_c);                   // 위로
    } else {
        if (cur_r != 1 && cur_c != 1 && cur_r != R && cur_c != C) // 그 어느 모서리도 아니라면
            return make_pair(cur_r, cur_c + 1);                   // 오른쪽으로
        if (cur_c == C && cur_r != 1)                             // 오른쪽 끝이지만, 모서리는 아니라면
            return make_pair(cur_r - 1, cur_c);                   // 위쪽으로
        if (cur_r == 1 && cur_c != 1)                             // 위쪽 끝이지만, 모서리는 아니라면
            return make_pair(cur_r, cur_c - 1);                   // 왼쪽으로
        else                                                      // 왼쪽 끝이라면
            return make_pair(cur_r + 1, cur_c);                   // 아래로
    }
}

void diffusionSimulation() { // 미세먼지 확산 시뮬레이션
    vector<vector<int>> dust_prefix(R + 1, vector<int>(C + 1, 0));
    for (int r = 1; r <= R; ++r) {
        for (int c = 1; c <= C; ++c) {               // 원본 맵에서, 미세먼지 위치 탐색
            if (map[r][c] != -1 && map[r][c] != 0) { // -1: 공기청정기도 아니고, 0: 비어있지도 않다면
                int spread_count = 0;                // 확산 횟수
                int spread_amount = map[r][c] / 5;   // 확산량
                if (spread_amount == 0)
                    continue; // 최적화: 확산 될 미세먼지양이 부족하면 그냥 스킵
                for (int i = 0; i < 4; ++i) {
                    int next_r = r + dr[i];
                    int next_c = c + dc[i];

                    if (next_r > 0 && next_c > 0 && next_r <= R && next_c <= C && map[next_r][next_c] != -1) { // VALID CHECK
                        dust_prefix[next_r][next_c] += spread_amount;                                          // ⌊A/5⌋ 만큼 확산
                        ++spread_count;
                    }
                }
                // 확산 이후, 출처 미세먼지량 감소: A - ⌊A/5⌋×(확산된 방향의 개수)
                dust_prefix[r][c] -= spread_amount * spread_count;
            }
        }
    }

    // 원본 맵의 모든 미세먼지 위치에서 확산 시뮬레이션 완료했으면, 원본 맵을 dust_prefix 만큼 합산
    for (int r = 1; r <= R; ++r) {
        for (int c = 1; c <= C; ++c) {
            map[r][c] += dust_prefix[r][c];
        }
    }
}

void windSimulation() { // 공기청정기 바람 시뮬레이션
    // 위쪽 공기청정기 (반시계)
    int cur_r = conditioner_upper_pos.first;
    int cur_c = conditioner_upper_pos.second;
    int prev_dust = 0;                // 이전 공간의 먼지
    cur_c += 1;                       // 오른쪽으로 이동하며 시작
    while (map[cur_r][cur_c] != -1) { // 공기청정기에 다시 도달할 때까지 반복
        // 현재 먼지를 prev_dust에 저장하고, 이전 먼지를 현재 공간에 대치
        int temp = prev_dust;
        prev_dust = map[cur_r][cur_c];
        map[cur_r][cur_c] = temp;

        pair<int, int> nextPos = getNextPos(cur_r, cur_c, false);
        cur_r = nextPos.first;
        cur_c = nextPos.second;
    }

    // 아래쪽 공기청정기 (시계)
    cur_r = conditioner_below_pos.first;
    cur_c = conditioner_below_pos.second;
    prev_dust = 0;                    // 이전 공간의 먼지
    cur_c += 1;                       // 오른쪽으로 이동하며 시작
    while (map[cur_r][cur_c] != -1) { // 공기청정기에 다시 도달할 때까지 반복
        // 현재 먼지를 prev_dust에 저장하고, 이전 먼지를 현재 공간에 대치
        int temp = prev_dust;
        prev_dust = map[cur_r][cur_c];
        map[cur_r][cur_c] = temp;

        pair<int, int> nextPos = getNextPos(cur_r, cur_c, true);
        cur_r = nextPos.first;
        cur_c = nextPos.second;
    }
}

int main() {
    // 1-based index
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> R >> C >> T; // R*C 맵, T초 후 미세먼지 양
    map.assign(R + 1, vector<int>(C + 1, 0));
    for (int r = 1; r <= R; ++r) {
        for (int c = 1; c <= C; ++c) {
            cin >> map[r][c];
            if (map[r][c] == -1 && conditioner_upper_pos.first == -1) { // 아직 공기청정기 좌표가 등록되지 않았다면
                conditioner_upper_pos = {r, c};
                conditioner_below_pos = {r + 1, c};
            }
        }
    }

    while (T--) { // T초동안 시뮬레이션
        diffusionSimulation();
        windSimulation();
    }

    // 남아있는 미세먼지 양 계산
    int dust_count = 2; // 공기청정기(-1)이 두개 있으니까 경감 위해서 2로 초기화
    for (int r = 1; r <= R; ++r) {
        for (int c = 1; c <= C; ++c) {
            dust_count += map[r][c];
        }
    }

    cout << dust_count;

    return 0;
}

---

치즈 (골드 3 - 그래프 이론, 시뮬레이션)

N×M의 모눈종이 위에 아주 얇은 치즈가 <그림 1>과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 <그림 1> 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다.

<그림 2>와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부공기가 유입되면 <그림 3>에서와 같이 C로 표시된 치즈 격자들이 사라지게 된다.

모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다. 입력으로 주어진 치즈가 모두 녹아 없어지는데 걸리는 정확한 시간을 구하는 프로그램을 작성하시오.

<그림 1>

<그림 2>

<그림 3>

정리하자면, NxM의 격자판 모눈종이 위에 치즈 조각이 놓여져 있고, 외부 공기와 2변 이상 맞닿아 있는 치즈 조각은 1시간 뒤에 녹는다. 외부 공기가 아니라 치즈 내부의 공기와는 맞닿아 있어도 녹지 않는다.

따라서, 여기서 중요한 처리는 외부/내부 공기에 대해서다. 외부 공기와 내부 공기를 어떻게 구분할 것인가?

이 문제를 보자마자 떠오른 내 아이디어는 다음과 같았다:

2차원 정수 벡터로 맵을 저장한다.
[0: 공기, 1: 치즈, -1: 맵 가장자리, 2: 외부 공기]
여기서 외부 공기란 맵의 가장자리와 인접해 있는 공기이기 때문에,
각 공기에 대해서 맵의 가장자리와 닿는 루트가 있다면 외부. 아니라면 내부 공기라고 판단할 수 있다.

문제의 본문에서 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다." 라고 했음으로
맵의 가장자리를 -1로 표시할 수 있다(외부)

탐색 이전에 모든 -1 혹은 2로부터 인접 BFS 탐색을 시작해서 만나는 모든 공기(0)를 외부 공기(2)로 대체한다.
모든 치즈에 대해서 인접한 외부 공기(2)혹은 가장자리(-1)를 검색한다. 2변 이상이 인접해있으면 치즈 격자를 삭제한다.

유의사항: 치즈가 녹는 현상은 동시에 일어난다. 순서가 영향을 미치지 않는다.

이렇게 처음 맵을 입력받고 나서, 가장자리 부분을 외부 공기라고 표시하고 외부 공기와 인접한 모든 공기를 외부 공기로 표시했다. 이런 일련의 과정을 거치는 함수를 만들었다. determineOutSideAir();

그리고, 맵에 존재하는 모든 치즈를 찾고 인접 격자를 확인해서 치즈를 녹이는 시뮬레이션 함수 cheeseMeltSimulation();도 작성했다.

여기서 주의할점은, 이전 문제에도 비슷한 유의사항이 있었는데 치즈가 녹는 현상은 정확히 '동시에' 일어난다는 것이다. 순차적으로 처리했다간 방금 녹은 치즈가 인접한 치즈의 탐색이 진행 될때 외부 공기로 판단되어서 녹지 않았어야 할게 녹을수도 있다. 따라서 한번에 원본 맵에 시뮬레이션 상황을 업데이트 하지 않고, 따로 정보를 담아두었다가 시뮬레이션이 모두 종료되면 한번에 일괄적 업데이트를 했다.

문제는 전체적으로 쉬웠다. 외부/내부 공기를 어떻게 분간하냐가 이 문제의 어려운 부분이었던 것 같은데. 아이디어를 생각해내는 과정이 어렵지 않았고 직관적이었다.

다만 구현량이 많아서 실수하기 쉬웠다. 나도 실수를 한번 했는데. for문에서 index로 사용하는 변수 r과 queue에서 .front로 받아온 int cur_r 을 헷갈려서 실수를 했다.

다음부터는 for index r의 이름을 r이 아니라 fr 혹은 ir로 해서 for문의 인덱스로 사용되는 변수임을 내가 쉽게 알아차릴 수 있도록 습관을 변경해보자 한다.

// 백준: 치즈
// https://www.acmicpc.net/problem/2638
// 2024-06-03

/*
간단한 BFS 탐색인데, 외부 공기와 내부 공기를 어떻게 구분할 것인가?
내 생각:
2차원 정수 벡터로 맵을 저장한다.
[0: 공기, 1: 치즈, -1: 맵 가장자리, 2: 외부 공기]
여기서 외부 공기란 맵의 가장자리와 인접해 있는 공기이기 때문에,
각 공기에 대해서 맵의 가장자리와 닿는 루트가 있다면 외부. 아니라면 내부 공기라고 판단할 수 있다.

문제의 본문에서 "모눈종이의 맨 가장자리에는 치즈가 놓이지 않는 것으로 가정한다." 라고 했음으로
맵의 가장자리를 -1로 표시할 수 있다(외부)

탐색 이전에 모든 -1 혹은 2로부터 인접 BFS 탐색을 시작해서 만나는 모든 공기(0)를 외부 공기(2)로 대체한다.
모든 치즈에 대해서 인접한 외부 공기(2)혹은 가장자리(-1)를 검색한다. 2변 이상이 인접해있으면 치즈 격자를 삭제한다.

유의사항: 치즈가 녹는 현상은 동시에 일어난다. 순서가 영향을 미치지 않는다.
*/

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

int N, M;                // 모눈종이 크기 N*M
vector<vector<int>> map; // 모눈종이 맵

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

void determineOutsideAir() { // 외부 공기 판단
    // 방문 배열은 필요 없을 것 같다: map의 정보를 2로 바꾸는 것이 방문 배열의 역할을 함
    // 모든 -1, 2에 대해서 주변 0으로 BFS. 2로 치환
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            if (map[r][c] == -1 || map[r][c] == 2) { // -1 혹은 2 발견
                queue<pair<int, int>> q;
                q.push({r, c});
                // BFS 시작
                while (!q.empty()) {
                    int cur_r = q.front().first;
                    int cur_c = q.front().second; // 여기서 q의 (r, c)값을 cur_r, cur_c로 정의했는데 아래의 if문에서는 for문의 인덱스 r, c를 쓰고 있었다. 실수.
                    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 < M && map[next_r][next_c] == 0) { // VALID CHECK
                            map[next_r][next_c] = 2;                                                            // 외부 공기라고 표시
                            q.push({next_r, next_c});
                        }
                    }
                }
            }
        }
    }
}

bool cheeseMeltSimulation() { // 치즈 녹음 시뮬레이션
    // 원본 맵을 보존하기 위해서, 녹을 치즈를 바로 맵에서 지우지 않고 좌표를 저장해놨다가 모든 치즈에 대한 연산이 끝난 뒤 맵을 업데이트한다.
    vector<pair<int, int>> meltedCheese;

    // 맵에서 치즈를 찾는다 (가장자리 제외)
    int cheeseCount = 0; // 맵의 치즈 개수를 추적하기 위한 함수
    for (int r = 1; r < N - 1; ++r) {
        for (int c = 1; c < M - 1; ++c) {
            if (map[r][c] == 1) { // 현재 (r, c)가 치즈라면
                ++cheeseCount;    // 치즈 개수 업데이트
                int outsideAirCount = 0;
                for (int i = 0; i < 4; ++i) { // 인접 격자에 2(외부공기) 혹은 가장자리(-1)가 있는지 확인
                    int next_r = r + dr[i];
                    int next_c = c + dc[i];
                    if (next_r >= 0 && next_c >= 0 && next_r < N && next_c < M && (map[next_r][next_c] == 2 || map[next_r][next_c] == -1)) { // VALID CHECK
                        ++outsideAirCount;                                                                                                   // 카운트 증가
                    }
                }
                if (outsideAirCount >= 2)
                    meltedCheese.push_back({r, c}); // 2변 이상 외부 공기와 맞닿아 있다면 현재 격자를 녹은 치즈 목록에 추가
            }
        }
    }

    if (meltedCheese.size() == cheeseCount) // 녹은 치즈가 맵에 남아있던 치즈 개수와 같다면, 모든 치즈가 녹은 것이므로 true 반환.
        return true;

    // 녹은 치즈를 맵에 반영한다
    for (const auto &next : meltedCheese)
        map[next.first][next.second] = 2;

    return false;
}

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

    cin >> N >> M; // 모눈종이 크기 N*M
    map.assign(N, vector<int>(M, 0));

    // 맵 입력받기
    int cheeseCount = 0;
    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < M; ++c) {
            cin >> map[r][c];
            if (map[r][c] == 1)
                ++cheeseCount;
        }
    }

    if (cheeseCount == 0) { // 엣지 케이스 처리 : 치즈가 아예 없을 때
        cout << "0";
        return 0;
    }

    // 가장자리를 - 1로 표시
    for (int c = 0; c < M; ++c) {
        map[0][c] = -1;
        map[N - 1][c] = -1;
    }
    for (int r = 0; r < N; ++r) {
        map[r][0] = -1;
        map[r][M - 1] = -1;
    }

    int counter = 1;
    while (true) {
        determineOutsideAir();        // 외부 공기 업데이트
        if (cheeseMeltSimulation()) { // false면 치즈 남아있음, true면 치즈 없음.
            break;
        }
        ++counter;
    }

    cout << counter;

    return 0;
}

---

끝.

이렇게 6월 4일까지의 PS 회고 끝.
현재 시각 6월 4일 오후 1시 34분인데, 아직 어제의 잠을 자지 않았다.
휴 :(

지난 몇주간 생활패턴이 심하게 꼬여서, 오늘 하루를 새고 패턴을 되찾으려고 한다..

이제 Solved.ac 클래스 4 금장까지 2문제 남았다.
확실히 시간이 지날수록 내 실력의 상승이 느껴진다.
골드 하위 문제가 이제 쉽게 느껴진다. 클래스 5에 진입한다면 이런 성장폭을 한번 더 겪게 되겠지.

올해 목표는 넉넉잡아서 플래티넘 달성이었는데. (왜냐면 그 이전에 골드 이하의 기본기를 모두 갖추고 싶었다. 아주 견고하게)

생각보다 일찍 달성할지도 모르겠다. 끝!