플레티넘으로 가는 길 - 완주

 

인사

안녕하세요, 오랜만에 포스팅을 하게 되었습니다.
최근에 좀 슬픈 일이 있어서 좀 다운된 상태였는데요.
하지만 이제는 훌훌 털어내고 다시 일어나기 위해 이렇게 글을 쓰게 되었습니다.

오늘은 드디어! 제가 플래티넘을 달성했습니다 🎉
(사실 조금 시간이 지나긴 했지만요)

이번 글에서는 그 과정에서 풀었던 문제 하나를 소개하고,
앞으로의 계획에 대해서도 함께 이야기해보려 합니다.

문제 소개 

오늘 소개할 문제는 2-SAT(2-Satisfiability) 문제입니다.
이 글에서는 2-SAT의 개념과, 이를 해결하는 데 꼭 필요한 SCC(Strongly Connected Component, 강한 연결 요소) 개념,
그리고 SCC를 효율적으로 구하기 위한 Tarjan 알고리즘에 대해 함께 다뤄보겠습니다.

제가 예시로 선택한 문제는 바로 백준 3648번 — 아이돌 문제입니다.

문제 링크

이 문제는 2-SAT 개념을 제대로 이해하지 못하면 사실상 풀기 매우 어려운 문제입니다.
2-SAT 문제에서는 논리식을 만족시킬 수 있는 변수 조합을 찾아야 하는데,
이 과정에서 SCC를 구하는 작업이 필수적으로 들어가게 됩니다.

따라서 이번 포스팅에서는
1. 2-SAT의 기본 개념
2. SCC(강한 연결 요소)의 의미
3. SCC를 효율적으로 찾는 Tarjan 알고리즘

이 세 가지를 중심으로 설명드리겠습니다.

문제 분석

- 문제 링크: 백준 3648번 - 아이돌
- 난이도: 플래티넘 3

문제를 간단히 요약하면 다음 세 가지 조건으로 정리할 수 있습니다.

1. 1번 참가자인 상근이는 반드시 합격해야 한다.
2. 각 심사위원의 두 표 중 적어도 하나는 그대로 반영되어야 한다.
3. 모든 심사위원이 만족할 수 있는 결과라면 "yes", 아니라면 "no"를 출력해야 한다.
(즉, 만족스러운 결과가 나와야 ‘해킹’이 가능하다는 설정입니다.)

입력 조건

• n: 참가자의 수 (2 ≤ n ≤ 1000)

• m: 심사위원의 수 (1 ≤ m ≤ 2000)

• 각 심사위원은 두 표를 던지며,

  • +a는 a번 참가자 찬성표,

  • -a는 a번 참가자 반대표를 의미합니다.

입력은 (n, m) 쌍으로 시작하며, 이후 m개의 투표 정보가 주어집니다.
이를 반복적으로 받아서 상근이(1번) 가 반드시 합격할 수 있는지를 판단해야 합니다.
결과적으로 "yes" 또는 "no" 를 출력하는 것이 목표입니다.

문제 핵심 아이디어

문제만 보면 단순히 "투표 결과를 조합하는 시뮬레이션"처럼 보이지만,
사실상 조건을 동시에 만족시키는 경우의 수를 찾아야 하기 때문에 단순 탐색으로는 해결이 어렵습니다.

그래서 저는 다음과 같은 사고 과정을 거쳤습니다.

1. 각 심사위원의 두 표 중, 적어도 한 표가 맞아야 한다.
→ 이를 논리식으로 표현하면 (A ∨ B) 형태의 조건이 됩니다.

2. 이 조건을 만족시키는 전체 조합을 찾는 방법은 무엇일까?
→ 바로 2-SAT(2-Satisfiability) 가 이 문제의 핵심 패턴이라는 점을 떠올렸습니다.

3. 그렇다면 2-SAT을 어떻게 구현할까?
→ 2-SAT을 풀기 위해선 SCC(Strongly Connected Component) 를 구해야 하며,
이를 효율적으로 찾기 위해 Tarjan 알고리즘을 적용하기로 했습니다.

결국 이 문제는

“심사위원들의 논리식을 모두 만족시킬 수 있는지 여부를 판단하는 2-SAT 문제”

로 해석할 수 있으며,
이때 SCC 분석으로 모순 여부를 파악해 답을 구할 수 있습니다.

전체 코드

#include <bits/stdc++.h>

using namespace std;

int transitNum(const int x) {

  if ( x < 0 ) return 2 * abs(x);

  else return 2 * abs(x) - 1;

}

void sat2(

vector<vector<int>>& matrix,

const int a, const int b

) {

  int x1 = transitNum(a * -1), y1 = transitNum(b);

  matrix[x1].push_back(y1);

 

  int x2 = transitNum(a), y2 = transitNum(b * -1);

  matrix[y2].push_back(x2);

}

void dfs(

vector<vector<int>>& matrix, const int node,

vector<int>& disc, vector<int>& low, vector<vector<int>>& scc, vector<int>& stack, vector<bool>& inStack, int& timer

) {

 

  disc[node] = low[node] = ++timer;

  stack.push_back(node);

  inStack[node] = true;

 

  vector<int>& targetMatrix = matrix[node];

 

  for ( int i = 0; i < targetMatrix.size(); i++ ) {

   

    int newNode = targetMatrix[i];

   

    if ( disc[newNode] == -1 ) {

      dfs(matrix, newNode, disc, low, scc, stack, inStack, timer);

      low[node] = min(low[node], low[newNode]);

    } else if ( inStack[newNode] ) {

      low[node] = min(low[node], disc[newNode]);

    }

  }

 

  if ( disc[node] == low[node] ) {

   

    vector<int> sccNode;

   

    while ( true ) {

     

      int canNode = stack.back(); stack.pop_back();

      inStack[canNode] = false;

     

      sccNode.push_back(canNode);

     

      if ( canNode == node ) break;

    }

    scc.push_back(sccNode);

  }

}

int main(void) {

 

  // set

  ios::sync_with_stdio(false);

  cin.tie(nullptr);

 

  // n, m

  int n, m;

 

  while ( cin >> n >> m ) {

   

    const int maxN = 2 * n + 1;

    vector<vector<int>> matrix(maxN);

   

    // sangen access

    matrix[transitNum(-1)].push_back(transitNum(1));

   

    for ( int i = 0; i < m; i++ ) {

      int a, b; cin >> a >> b;

     

      sat2(matrix, a, b);

    }

   

    // tarjan

    vector<int> disc(maxN, -1);

    vector<int> low(maxN, -1);

    vector<vector<int>> scc;

    vector<int> stack; stack.reserve(maxN);

    vector<bool> inStack(maxN, false);

    int timer = 0;

 

    for ( int i = 1; i < maxN; i++ ) {

      if ( disc[i] == -1 ) dfs(matrix, i, disc, low, scc, stack, inStack, timer);

    }

   

    // check

    vector<int> group(maxN);

   

    for ( int i = 0; i < scc.size(); i++ ) {

      vector<int>& sccNode = scc[i];

      int root = sccNode.back();

     

      for ( int j = 0; j < sccNode.size(); j++ ) {

        int sccNumber = sccNode[j];

        group[sccNumber] = root;    

      }

    }

   

    // answer

    bool yes = true;

    for ( int i = 1; i < n + 1; i++ ) {

      int x = transitNum(i), y = transitNum(i * -1);

     

      if ( group[x] == group[y] ) {

        yes = false;

        break;  

      }

    }

   

    if (yes) cout << "yes" << '\n';

    else cout << "no" << '\n';

  }

 

  return 0;

}

성능 결과

• 메모리: 2048KB

• 실행 시간: 32ms

 

풀이 방향

이번 풀이에서는 전체 흐름을 다음 세 가지 핵심 포인트로 나누어 설명드리겠습니다.

1. 심사위원의 투표(찬성/반대)를 2-SAT 논리식으로 변환하는 방법

• 각 투표 (a, b)를 “둘 중 하나는 반드시 참이어야 한다”는 의미의 (A ∨ B)로 해석합니다.

• 이 조건을 만족시키기 위해 (¬A → B)와 (¬B → A)의 함의 그래프(Implication Graph) 로 변환합니다.

2. SCC(Strongly Connected Component) 구성 및 Tarjan 알고리즘 적용

• 2-SAT에서는 어떤 변수 x와 ¬x가 같은 SCC에 속한다면 모순이 발생합니다.

• Tarjan 알고리즘을 이용해 각 정점의 SCC를 효율적으로 탐색합니다.

3. 정답 판별 로직 (yes / no)

• 각 변수 x와 ¬x가 동일한 SCC에 포함되어 있으면 “no”,
  그렇지 않다면 “yes” 로 출력합니다.

• 또한 문제의 조건에 따라 1번(상근이) 은 반드시 참이 되도록 제약을 추가했습니다.

1. 2-SAT의 개념 및 풀이

1-1. 2-SAT의 핵심 개념

int transitNum(const int x) {

  if ( x < 0 ) return 2 * abs(x);

  else return 2 * abs(x) - 1;

}

void sat2(

vector<vector<int>>& matrix,

const int a, const int b

) {

  int x1 = transitNum(a * -1), y1 = transitNum(b);

  matrix[x1].push_back(y1);

 

  int x2 = transitNum(a), y2 = transitNum(b * -1);

  matrix[y2].push_back(x2);

}

2-SAT(2-Satisfiability) 문제의 핵심은
여러 개의 논리식이 모두 참(true)이 되도록 변수의 참/거짓 값을 조합하는 것입니다.

예를 들어 아래와 같은 식이 있다고 가정해봅시다.

```css

(a ∨ b) ∧ (¬b ∨ c) ∧ ...

```

여기서 (a ∨ b)는 “a 또는 b 중 하나만 참이면 된다”는 뜻입니다.
이 조건을 만족시키기 위해서는 다음 두 가지 함의(Implication) 가 성립해야 합니다.

• ¬a → b

• ¬b → a

이유는 간단합니다.
만약 a가 거짓이라면(¬a 참), b는 반드시 참이어야 (a ∨ b)가 참이 되기 때문이고,
반대로 b가 거짓이라면(¬b 참), a는 반드시 참이어야 조건을 만족할 수 있기 때문입니다.

즉 (a ∨ b)는 “¬a → b”와 “¬b → a”를 모두 만족하면 참이 됩니다.
이 논리적 관계를 그래프 형태로 표현하면, 2-SAT 문제는 곧 방향 그래프 탐색 문제가 됩니다.

1-2. 문제에의 적용

이 문제에서는 참가자 번호 앞의 부호로 찬성/반대 여부를 표현합니다.

• +a → a번 참가자 찬성표

• -a → a번 참가자 반대표

이때 각 참가자에 대해 다음과 같이 번호를 변환했습니다.

구분	계산식	의미
찬성(+a)	2 * a - 1	True 노드
반대(-a)	2 * a	False 노드

즉, 참가자마다 두 개의 노드를 가지게 되며
하나는 참(True), 다른 하나는 거짓(False) 상태를 의미합니다.

transitNum() 함수는 이 변환을 담당하며,
sat2() 함수는 (a ∨ b) 조건을 함의 그래프로 바꾸어
vector<vector<int>> matrix에 간선 정보를 저장합니다.

이렇게 만들어진 matrix는
각 노드(참/거짓 상태)에서 도달 가능한 조건(다른 변수의 상태) 을 저장한 그래프로,
이후 Tarjan 알고리즘을 통해 SCC(Strongly Connected Component) 를 구하는 데 활용됩니다.

2. SCC (Strongly Connected Components, 강한 연결 요소)

[그림1] 출처: cp-algorithms.com 

 

2-1. SCC란 무엇인가?

2-SAT 문제를 그래프로 변환하면, 각 변수와 그 부정(¬)이 조건 간의 결합(implication) 으로 연결됩니다.
[그림1]을 보면 다음과 같은 결합 관계가 형성됩니다.

• (c)

• (a, b)

• (~b, ~a)

• (~c)

이렇게 서로 도달 가능한 노드 집합을 SCC(Strongly Connected Component, 강한 연결 요소) 라고 부릅니다.
즉, SCC 내부의 모든 노드는 서로에게 도달 가능한 관계입니다.

2-2. SCC를 구하는 대표 알고리즘

SCC를 구하는 대표적인 알고리즘은 두 가지가 있습니다.

알고리즘	특징
Kosaraju	두 번의 DFS를 수행. 직관적이고 구현이 간단하지만, 약간의 오버헤드 존재
Tarjan	한 번의 DFS로 SCC를 구함. 효율적이고 코드가 간결함

이전에는 Kosaraju 알고리즘을 주로 사용했지만,
이번 문제에서는 좀 더 깔끔하고 실전에서 자주 사용되는 Tarjan 알고리즘을 적용했습니다.

2-3. Tarjan 알고리즘의 핵심 아이디어

Tarjan 알고리즘은 DFS(깊이 우선 탐색)를 이용해 각 노드가 어떤 SCC에 속하는지를 판별합니다.
핵심 아이디어는 다음과 같습니다.

1. DFS 순서(disc): 각 노드가 DFS에서 처음 방문된 시점을 기록
2. Low-link 값(low): 해당 노드가 도달할 수 있는 가장 “이른” 방문 노드의 번호
3. Stack 관리: 탐색 중인 노드를 스택에 저장하고, SCC가 완성될 때까지 보관

2-4. 코드로 살펴보기

void dfs(

vector<vector<int>>& matrix, const int node,

vector<int>& disc, vector<int>& low, vector<vector<int>>& scc, vector<int>& stack, vector<bool>& inStack, int& timer

) {

 

  disc[node] = low[node] = ++timer;

  stack.push_back(node);

  inStack[node] = true;

 

  vector<int>& targetMatrix = matrix[node];

 

  for ( int i = 0; i < targetMatrix.size(); i++ ) {

   

    int newNode = targetMatrix[i];

   

    if ( disc[newNode] == -1 ) {

      dfs(matrix, newNode, disc, low, scc, stack, inStack, timer);

      low[node] = min(low[node], low[newNode]);

    } else if ( inStack[newNode] ) {

      low[node] = min(low[node], disc[newNode]);

    }

  }

 

  if ( disc[node] == low[node] ) {

   

    vector<int> sccNode;

   

    while ( true ) {

     

      int canNode = stack.back(); stack.pop_back();

      inStack[canNode] = false;

     

      sccNode.push_back(canNode);

     

      if ( canNode == node ) break;

    }

    scc.push_back(sccNode);

  }

}

2-5. 코드 해설

• disc[node]
  → 해당 노드를 처음 방문했을 때의 DFS 순서(타임스탬프)를 저장합니다.

• low[node]
  → DFS를 통해 도달 가능한 노드 중 가장 작은 disc 값을 저장합니다.
  즉, “이 노드가 도달할 수 있는 가장 상위 부모”를 의미합니다.

• stack / inStack
  → 현재 탐색 중인 경로에 있는 노드를 추적합니다.
  스택에 있는 노드끼리는 잠재적으로 같은 SCC에 속할 수 있습니다.

2-6. 동작 흐름

1. 아직 방문하지 않은 노드를 만나면 DFS를 시작하고, disc와 low를 현재 타이머 값으로 설정합니다.
2. 인접한 노드를 탐색하면서

• 아직 방문하지 않은 노드라면 재귀적으로 DFS를 호출

• 이미 방문했고 스택에 남아 있다면, 해당 노드의 disc 값을 이용해 low[node]를 갱신
  3.  DFS가 끝난 후, disc[node] == low[node]이면
  → 현재 노드는 하나의 SCC 루트(root) 이며,
  스택에서 루트 노드까지의 모든 노드를 하나의 강한 연결 그룹으로 묶습니다.

이 과정을 반복하면 전체 그래프가 여러 개의 SCC로 분리됩니다.
SCC에 속한 노드들은 서로 강하게 연결되어 있으므로,
같은 그룹 내에 어떤 변수와 그 부정이 함께 존재한다면 모순(contradiction) 이 발생하게 됩니다.

3. 정답 출력 (모순 검증 및 결과 결정)

3-1. 핵심 포인트

마지막 단계에서는 SCC 결과를 이용해 모순(contradiction) 이 존재하는지를 확인해야 합니다.
즉, 어떤 변수 x와 그 부정 ¬x가 같은 SCC 그룹에 속한다면,
논리적으로 “x가 참이면서 동시에 거짓인” 모순이 발생하게 됩니다.
이 경우 정답은 no 가 됩니다.

3-2. 상근이(1번)의 예외 처리

이 문제에서 중요한 점은 1번 참가자(상근이) 가 반드시 합격해야 한다는 조건입니다.
즉, 상근이는 항상 true 상태여야 하므로,
다음과 같은 추가 조건(함의 관계) 을 강제로 부여합니다.

이는 “상근이가 거짓일 수 없다”는 의미로,
그래프 상에서는 2 → 1 (즉, 반대표 노드에서 찬성표 노드로 이동) 의 간선을 추가하는 것입니다.
이 조건을 통해 상근이는 무조건 true 로 고정됩니다.

3-3. 그룹화 및 판별 로직

Tarjan 알고리즘을 통해 SCC를 모두 구한 후,
각 노드가 속한 그룹 번호를 저장합니다.

vector<int> group(maxN);

for (int i = 0; i < scc.size(); i++) {

  vector<int>& sccNode = scc[i];

  int root = sccNode.back();

  for (int node : sccNode)

    group[node] = root;

}

그다음, 각 변수 x 와 ¬x 가 같은 그룹에 속하는지를 확인합니다.

bool yes = true;

for (int i = 1; i <= n; i++) {

  int x = transitNum(i);

  int y = transitNum(-i);

  if (group[x] == group[y]) {

    yes = false;

    break;

  }

}

cout << (yes ? "yes\n" : "no\n");

- 두 노드가 같은 SCC에 속한다면 ⇒ 모순 발생 → "no"

- 한 번도 모순이 발생하지 않았다면 ⇒ 해킹 가능 → "yes"

3-4. 직관적으로 이해하기

초기에 ¬x → x (즉, 거짓이면 반드시 참이 되어야 함)를 참으로 가정하고 SCC를 검사합니다.
이 과정에서

• 만약 x → ¬x 도 존재한다면 두 노드는 서로 도달 가능,

• 결국 같은 SCC 그룹에 속하게 되어 모순이 발생합니다.

따라서 “¬x → x는 참이지만 x → ¬x는 거짓”이라면 문제가 없고,
이때는 상근이가 반드시 합격하는 정상적인 해킹이 가능한 상황입니다.

3-5. 예시로 살펴보기

다음 조건이 주어졌다고 가정해봅시다.

(1, 2), (-2, -3), (2, 4)

이 경우 [그림2]와 같은 그래프가 형성되며,
각 변수 간에는 강한 결합(SCC)이 생기지 않습니다.

비록 ¬1 → 1 (즉, -1 → 1) 관계가 존재하지만,
1 → ¬1 이 성립하지 않기 때문에 상호 도달 불가능 → 모순 없음 → "yes" 출력

하지만 반대로 두 방향이 모두 연결되어 있다면,
즉 ¬1 → 1 그리고 1 → ¬1 모두 참이라면,
이는 x와 ¬x가 같은 SCC에 속하는 완전한 모순으로,
결과는 "no" 가 됩니다.

[그림2] (1, 2), (-2, -3), (2, 4)의 그래프

마무리 

오늘은 SCC(강한 연결 요소), 2-SAT, 그리고 Tarjan 알고리즘을 이용해 문제를 해결하는 과정을 소개해드렸습니다.
사실 한 번 이 알고리즘의 개념만 제대로 이해하면,
이 문제 자체는 생각보다 어렵지 않다는 걸 느낄 수 있습니다.
다만 2-SAT의 논리적 구조나 Tarjan 알고리즘의 구현 과정이

집합론적 사고와 깊은 연관이 있기 때문에, 처음 접할 땐 다소 난해하게 느껴질 수 있습니다. 

플래티넘 달성까지의 여정은 개인적으로 꽤 의미 있는 시간이었습니다.
골드 티어를 달성할 때까진 약 3주 정도밖에 걸리지 않았지만,
플래티넘까지는 무려 3~4개월 정도가 걸렸습니다.
그만큼 더 깊게 사고하고, 문제를 구조적으로 접근해야 했기 때문이죠.

그래서 처음 플래티넘을 달성했을 때의 기쁨은 정말 컸습니다.
이제는 그 이름에 걸맞게 골드 난이도 문제는 자신 있게 풀 수 있는 개발자,
그리고 꾸준히 플래티넘 문제를 연습하며 한 단계 더 성장한 실력자가 되는 것이 목표입니다.

💎 다음 목표는 다이아몬드입니다.
물론, 다이아몬드는 많은 사람들이 “평생 한 번도 달성하기 어려운 등급”이라고 말합니다.
하지만 저는 수학적 사고를 좋아하고, 논리적인 문제 풀이에 흥미를 느끼기 때문에
도전해볼 충분한 가치가 있다고 생각합니다.

앞으로는 “플래티넘 실력 다지기”에 집중하면서,
차근차근 다이아몬드를 향해 나아가보려 합니다.

읽어주신 모든 분들께 감사드리며,
하시는 일 모두 잘되시길 바랍니다.
오늘도 화이팅입니다!