코딩하는 사자

문제 정보

• 문제 링크
• 요약: Outdegree가 1인 그래프에서 cycle을 판별하고, cycle에 속하는 노드 구하기

• Algorithm: `Graph`, `DFS`
• 난이도: Gold 3 ('24. 9. 15. 기준)
• 출처: solved.ac class 5 에센셜

풀이

가정: 학생들을 노드, 한 학생이 선택한 학생간의 관계를 방향이 있는 간선(directed edge)으로 하자.

접근 1

• 조건1: $n \le 10^5$
• 접근1: cycle이 되어야 한 팀이기 때문에 cycle 판별을 dfs로 naive하게 푼다면
  • 모든 노드들에서 dfs를 수행하여 다른 노드들을 탐색
  • 방문했던 노드를 또 방문한다면 cycle이 있는 것이고, 그 cycle에 속하는 학생들은 한 팀
  • 제한: $O(n^2) = 10^5 \times 10^5$ = TLE
  • 따라서 $O(n)$ or $O(n \log n)$ 인 솔루션이 필요할 듯 하다.

접근 2

• 조건2: 한 학생은 한 명의 학생만 선택하기 때문에 각 노드들은 outdegree가 1이다.
• 접근2: 위의 조건에 의해 두 노드 간의 경로는 유일하다!
  • 위의 조건을 어떻게 사용할 수 있을까?
  • 먼저 아래와 같은 $O(n)$ 가정을 하자
    • 가정: A에서 시작한 dfs와 이후 B에서 시작한 dfs는 독립적이지 않다
      
      • 즉, 이전 dfs 탐색에서 이미 한번 방문했던 노드들은 또 방문하지 않는다.
  • 이런 상황에서 탐색 중 방문했던 노드를 만난다면 둘 중 한가지이다!
    • Case1: 이전 탐색에서 방문을 했거나
    • Case2: 현재 노드와 방문할 노드가 cycle에 속하거나
    • 위의 두가지 경우를 구분할 수 있는 방법은
      • 이번 탐색(dfs) 간 방문 했던 노드들을 저장하고
      • 다음 방문할 노드가 이미 방문되어있고, 방문 노드 리스트에 있다면
      • 다음 방문할 노드부터 현재 노드까지는 cycle이다.

검증

• 추론1: 두 노드 사이의 경로가 유일하기 때문에 한 cycle에 속하는 원소들은 다른 cycle에 속하지 않게 된다.
• 추론2: 한 탐색에서 이전 탐색이든, 이번 탐색이든 방문했던 노드에 도달했으면 더 이상 탐색을 진행시킬 이유가 없다.
  • outdegree가 1개이기 때문에 방문했던 노드들이 갈 수 있는 노드들은 모두 방문했다.
  • 방문 노드 리스트를 최대 1번 확인하고 탐색을 종료하니 $O(n)$으로 해결 가능하다.
• 추론3: 한 탐색에서 cycle을 확인한 노드는 다음 탐색 때 다시 확인할 필요가 없다.
  • 위의 접근2-가정 이 틀린 가정이 아니라는 사실을 확인할 수 있다!

예시

• 1번에서 dfs를 시작 (1번 탐색)
  • `1 -> 2 -> 3 -> 4` 순으로 탐색 진행 후
  • 1번 노드를 만나고, 이는 이미 방문했던 노드임
  • 따라서 방문 리스트를 확인하면 `[1, 2, 3, 4]`이고
  • 1번 노드는 방문 리스트에 들어있기 때문에 1, 2, 3, 4번 노드는 cycle이다.
• 탐색이 끝난 뒤 2, 3, 4번 노드는 이전 탐색에서 방문했기 때문에 탐색 시작에서 무시
• 이후 5번으로 dfs를 시작 (2번 탐색)
  • 1번 노드를 만나고, 이는 이미 방문했던 노드임
  • 따라서 방문 리스트를 확인하면 `[5]`이고
  • 1번 노드는 방문 리스트에 없기 때문에 5는 cycle에 속하지 않는다.

코드

main은 단순히 테스트케이스를 반복 + 빠른 입출력 설정하는 역할이라 solve, dfs 함수만 확인하면 된다

// Baekjoon09466.cpp
#include <iostream>

#include <vector>
#include <algorithm>

using namespace std;

vector<int> stck; // 이번 탐색 간 방문한 노드 리스트
int teamNum, teamInfo[100'001]; // 각 노드들의 팀 정보
int adjList[100'001]; // outdegree가 1이기 때문에 단순 배열로 선언
bool visited[100'001]; // 우리 모두가 아는 visited

void dfs(int curr) {
    visited[curr] = true;
    stck.push_back(curr);

    int next = adjList[curr];
    if (!visited[next])
        dfs(next);
    else {
        int nextIdx = 0;
        // 다음 방문할 노드가 방문 노드 리스트에 있는지 확인
        for (nextIdx = 0; nextIdx < stck.size() && stck[nextIdx] != next; nextIdx++);
        
        // 방문 노드 리스트에 존재하다면 cycle 체크
        if (nextIdx <= stck.size()) {
            for (; nextIdx < stck.size(); nextIdx++)
                teamInfo[stck[nextIdx]] = teamNum;
            teamNum++;
        }
    }

    stck.pop_back();
}

void solve() {
    int n;
    cin >> n;

	// 자원들이 테스트케이스마다 구분되지 않으므로 매번 초기화
    teamNum = 1;
    fill(visited, visited + n + 1, false);
    fill(teamInfo, teamInfo + n + 1, 0);

    for (int i = 1; i <= n; i++)
        cin >> adjList[i];

    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {
            dfs(i);
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!teamInfo[i])
            ans++;

    cout << ans << '\n';
}

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

    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

잡담

SCC 느낌도 나는 굉장히 재밌는 신박한 문제였다.

outdegree가 1인 그래프에서는 $O(n)$으로 cycle detection을 할 수 있다는 점이 신기하기도 했다.

만약 한 노드의 outdegree가 1보다 크다면, 위의 방법으로 cycle에 속하는 원소들을 구할 수 없다.

(직접 해보면 된다!)

즉, 일반적인 graph의 cycle 판별이 아니라는 것!

특수한 경우이기 때문에 이 문제를 시간 안에 풀 수 있었음

풀이를 생각해내는 것보다 풀이를 남들이 이해가 되도록 글로 쓰는 것은 굉장히 어려운 작업이라는 것을 다시 한번 느꼈다.

거기다가 틀린 풀이가 아니라는 것을 생각해 내는 것 또한 어려웠다!

물론 틀린 풀이거나 틀린 부분이 있다면 알려주세요!

사이클 판별이라 Union-Find 인가 했지만 detection 뿐만 아니라 노드들을 탐색해야하므로 적절하지 못하다고 생각했다.

문제 설명

• 문제 링크
• Algorithm: DP, Knapsack

• 난이도: Gold 3 ('24. 9. 11.)
• 출처: solved.ac class5+
• 요약: 적절히 $i$개의 앱을 비활성화해서 $M$ 바이트 이상을 확보하되 $c$를 최소화

풀이

접근1

• 조건 1: $(n \le 100), \ (M, \ m_i \le 10^7), \ (c_i \le 100)$
• 접근 1: Naive하게 접근해보자. 각 앱은 활성화/비활성화 상태 2가지이고 앱이 최대 100개이니 경우의 수는 $2^{100}=10^{30}$이므로 TLE!

접근2

• 접근 2: 재귀적 구조를 찾고, 중복이 발생하는지 찾아보자 (DP로 풀 수 있는지 확인)
  • 앱이 5개 있다고 가정했을 때 선택할 수 있는 모든 경우의 수를 구해보자
    • 1번째 앱을 선택했다면 (1, 0, 0, 0, 0) 등으로 표시하고, 그 노드로 인해 파생되는 경우의 수들을 연결하였다.

    • 

  • 위와 같으며 무수히 많은 중복이 발생하므로 DP를 적용할 수 있겠다.
  • dp[i]를 i번째 앱을 선택했을 때 구할 수 있는 가장 작은 cost라고 해보자 (우리가 구하려고하는 값은 cost이니)
  • 하지만 우린 byte 정보도 무시할 수 없으니 dp[i][j] 형태로 i번째 앱을 선택하고 j Byte 인 경우 중 가장 작은 cost라 정의하자
  • $dp[i][j] = \min_{k = i + 1 \ to \ n}(dp[k][j - cost[i]])$
    • i를 선택한 뒤, i + 1을 선택해보고, i + 2를 선택해보고, ... n을 선택해보고 중 가장 작은 cost를 구하기
  • 위와 같이 전형적인 Knapsack 형태의 점화식을 구할 수 있다.
• 제한 1: 하지만 $M \le 10^7$이기 때문에 최악의 경우 위 점화식의 공간복잡도는 $O(10^9)$ 이므로 MLE가 발생한다.
  • 따라서 주어진 문제를 해결할 수 없다. 시간복잡도 또한 $O(n \times n \times M) = 10^{11}$ 이므로 TLE가 발생한다.
• 의문점 1: $c_i \le 100$
  • 비용이 굉장히 작은데 이유가 있을까? 비용을 DP의 한 차원으로 넣어볼까?

접근3

• 접근 3: dp[i][j]를 i번째 앱을 선택했을 때 비용이 j인 경우 중 가장 큰 Byte라 정의하자
  • 가장 큰 Byte인 이유? 우리는 M Byte 이상의 앱을 비활성화 시켜야하기 때문에 같은 비용이라면 큰 용량을 줄이는게 맞다!
  • 점화식: $dp[i][j] = \max_{k = i + 1 \ to \ n }(dp[k][j - byte[i]])$
  • 시간 복잡도: $O(n^3 \cdot c) = 10^8$으로 이론상으로는 성공한다!
    • 이유? i의 최대치 100($n$), 모든 앱의 비용이 100($c$)이고 100($n$)개를 선택한 경우를 j의 최대치로 설정해야함, 이후 한 점당 n번 반복
    • 따라서 $n \times n \times c \times n$
• 최적화
  • 하지만 위에 점화식은 쓸데 없는 계산이 많다
  • dp[j]를 비용이 j인 경우 가장 큰 Byte로 정의해보면 어떨까?
  • $dp[j] = \max_{i = 1 \ to \ n}(dp[j - cost[i]])$
  • 시간 복잡도: $O(n^2 \cdot c)$

코드

// Baekjoon07579.cpp
#include <iostream>

using namespace std;

using pii = pair<int, int>;

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

    int n, m;
    cin >> n >> m;

    pii app[100]; // { byte, cost }
    int dp[10'001] = { 0, };
    for (int i = 0; i < n; i++)
        cin >> app[i].first;
    for (int i = 0; i < n; i++)
        cin >> app[i].second;

    for (int i = 0; i < n; i++) {
        for (int j = 10'000; j >= 0; j--) { // 0부터 증가하게 되면 자기 자신을 선택했던 경우의 수에 또 자기자신을 더하므로 중복!
            int cost = j - app[i].second;
            if (cost >= 0 && dp[cost] != 0)
                dp[j] = max(dp[j], dp[cost] + app[i].first);
        }
        dp[app[i].second] = max(dp[app[i].second], app[i].first);
    }

    int ans;
    for (int i = 0; i <= 10'000; i++) {
        if (dp[i] >= m) {
            ans = i;
            break;
        }
    }

    cout << ans << '\n';

    return 0;
}

잡담

• 저 모든 경우의 수 다이어그램은 GPT 시킴 GPT 짱!
• 거스름돈 문제(동전 문제)로 치환가능 할 것 같아 Greedy 일 수도? 라고 생각했지만 그러기 위해서는 각 앱의 byte가 배수 관계여야하기 때문에 반드시 DP 겠거니 생각이 들어 DP로 고정관념을 박고 시작했다.
• 전형적인 Knapsack 같지만 무게(Byte)를 차원으로 두면 안되는 생각이 필요한 Knapsack이다. 전형적인 Knapsack은 추후 포스팅하겠다!
• 내가 썼지만 뭐라고 썼는지 잘 모르겠다. 내 생각을 글로 표현하는 것은 역시 어렵다. 조금 더 많이 연습해야겠다.

문제 설명

• 문제 링크
• Algorithm: Graph, BFS
• 난이도: Gold 5 ('24. 9. 1.)
• 출처: 춘식2팀 PS Study 5주차 공통문제

풀이

• 가정1: "각 회원"을 "노드", "회원 사이의 친구 관계"를 "간선"으로 나타내어 전체 관계를 그래프로 표현하자
• 조건1 : "두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다."
  • 즉, 두 회원 사이의 거리가 최단 거리를 그 회원 사이의 거리라고 한다는 뜻이다.
• 조건2: 직접 연결된 두 회원 사이의 거리는 무조건 1이다.
  • 최단 경로 알고리즘이 아닌 BFS로 풀어주자 (* 잡담 확인!)
    • 물론 n이 충분히 작아서 흔히 떠올리는 최단 경로 알고리즘(Dijkstra, Bellman-Ford, Floyd-Warshall)으로 풀어도 된다!
    • 하지만 PS는 가장 쉽게 풀 수 있는 방법을 선호하기에!
• 조건3: 회원의 점수는 그 회원에서 가장 멀리 있는 회원까지의 거리이다.
  • $score[i] = \max_{j = 1 \to n}(dis(i, j))$
  • 이 점수가 가장 낮은 사람들을 출력하면 답!

코드

// Baekjoon02660.cpp
#include <iostream>

#include <queue>
#include <vector>

using namespace std;

using pii = pair<int, int>;

// BFS로 모든 노드를 탐색하며 가장 먼 거리에 있는 노드까지의 거리를 반환
int getScores(vector<int> adjList[], int start) {
    queue<pii> q;
    bool visited[51] = { false, };

    q.push({ start, 0 });
    visited[start] = true;

    int result = 0;
    while (!q.empty()) {
        pii curr = q.front(); q.pop();
        result = max(result, curr.second);

        for (int& adjV : adjList[curr.first]) {
            if (!visited[adjV]) {
                visited[adjV] = true;
                q.push({ adjV, curr.second + 1 });
            }
        }
    }

    return result;
}

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

    int n;
    cin >> n;

    vector<int> adjList[51];

    int u, v;
    cin >> u >> v;
    while (!(u == -1 && v == -1)) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);

        cin >> u >> v;
    }

    int bossScore = 100;
    int scores[51] = { 0, };

    // 모든 회원의 점수를 구하며 가장 작은 점수를 저장
    for (int i = 1; i <= n; i++)  {
        scores[i] = getScores(adjList, i);
        bossScore = min(bossScore, scores[i]);
    }

    vector<int> boss;
    // 가장 작은 점수(= 회장 점수)와 동일한 점수를 가진 사람들을 회장 후보로 넣어줌
    for (int i = 1; i <= n; i++)
        if (scores[i] == bossScore)
            boss.push_back(i);

    cout << bossScore << ' ' << boss.size() << '\n';
    for (int i = 0; i < boss.size(); i++)
        cout << boss[i] << ' ';
    cout << '\n';

    return 0;
}

잡담

• 사실 BFS도 특정한 경우에 최단 경로를 구할 수 있기 때문에 최단 경로 알고리즘으로 포함 할 수 있다고 생각한다!
  • 특정한 경우: 가중치가 없거나 모든 간선의 가중치가 1인 경우
• 하지만 '통상' 최단 경로 알고리즘을 얘기할 때는 위에 언급한 3개를 말하니 구분해서 말한 것!

문제 설명

• 문제 링크
• Algorithm: Graph, BFS
• 난이도: Silver 2 ('24. 9. 1.)
• 출처: 춘식2팀 PS Study 5주차 공통문제

풀이

• 1차원 배열의 한 점에서 다른 한 점으로 가는 최소 거리를 구하는 문제
  • BFS!
• 한 점에서 갈 수 있는 점은 해당 점에 써져 있는 수!

코드

// Baekjoon11060.cpp
#include <iostream>

#include <queue>

using namespace std;

using pii = pair<int, int>;

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

    int n;
    cin >> n;

    int arr[1'000];
    for (int i = 0; i < n; i++)
        cin >> arr[i];

    queue<pii> q;
    bool visited[1'001] = { false, };

    q.push({ 0, 0 });
    visited[0] = true;

    int ans = -1;
    while (!q.empty()) {
        pii curr = q.front(); q.pop();

        if (curr.first == n - 1) {
            ans = curr.second;
            break;
        }

        for (int i = 1; i <= arr[curr.first]; i++) {
            int next = curr.first + i;
            if (next < n && !visited[next]) {
                visited[next] = true;
                q.push({ next, curr.second + 1 });
            }
        }
    }

    cout << ans << '\n';

    return 0; 
}

잡담

• DP로도 풀리는 문제!
  • $DP[i] = \min_{j = 1 \to (i-1)}(DP[j] + 1) \ (\text{if} \ j + arr[j] >= i)$

  // Baekjoon11060.cpp
  #include <iostream>
  
  using namespace std;
  
  int main(void) {
      ios_base::sync_with_stdio(false);
      cin.tie(0);
  
      int n;
      cin >> n;
  
      int arr[1'000], dp[1'000];
      for (int i = 0; i < n; i++) {
          cin >> arr[i];
          dp[i] = 0x3f3f3f3f;
      }
  
      dp[0] = 0;
      for (int i = 0; i < n; i++) {
          if (dp[i] != 0x3f3f3f3f) {
              for (int j = 1; j <= arr[i] && i + j < n; j++) {
                  dp[i + j] = min(dp[i + j], dp[i] + 1);
              }
          }
      }
  
      if (dp[n - 1] == 0x3f3f3f3f)
          cout << -1;
      else
          cout << dp[n - 1];
      cout << '\n';
  
      return 0;
  }

문제 설명

• 문제 링크
• Algorithm: Graph, BFS
• 난이도: Silver 1 ('24. 8. 30.)
• 출처: 춘식2팀 PS Study 5주차 공통문제

풀이

• 2차원 배열에서 한 점에서 다른 한 점으로 가는 최소 거리를 구하는 문제
  • BFS!
• 다만 한 점에서 상하좌우가 아닌 나이트가 이동할 수 있는 위치로만 이동할 수 있는 점이 다른 문제와의 다른 점!
• BFS의 중요한 점! 큐에 넣기 전에 visited 체크해줘야 한다!
  • 관련해서는 나중에 글을 작성해보겠다!

코드

// Baekjoon16948.cpp
#include <iostream>

#include <queue>

using namespace std;

using pii = pair<int, int>;

const int moves[6][2] = { { -2, -1 }, { -2, 1 }, { 0, -2 }, { 0, 2 }, { 2, -1 }, { 2, 1 } };

struct Node {
    int row, col;
    int time;

    Node(int r, int c, int t): row(r), col(c), time(t) { }
};

int main(void) {
    int n;
    cin >> n;

    pii start, end;
    cin >> start.first >> start.second >> end.first >> end.second;

    queue<Node> q;
    bool visited[200][200] = { { false, }, };

    q.push(Node(start.first, start.second, 0));
    visited[start.first][start.second] = true;

    int ans = -1;
    while (!q.empty()) {
        Node curr = q.front(); q.pop();
        if (curr.row == end.first && curr.col == end.second) {
            ans = curr.time;
            break;
        }

        for (int i = 0; i < 6; i++) {
            int newRow = curr.row + moves[i][0], newCol = curr.col + moves[i][1];
            if ((0 <= newRow && newRow < n) && (0 <= newCol && newCol < n)) {
                if (!visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;

                    q.push(Node(newRow, newCol, curr.time + 1));
                }
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

잡담

• 플젝 개발 때문에 PS를 많이 못하고 있다..! 얼른 끝내고 행복 백준해야지