백준 14926, Not Equal

개요

문제 링크
실버 1, Greedy
nC2만큼의 서로 다른 원소쌍 중 사전 순이 가장 빠른 방법 출력

---

접근

1. 어렵게 푸는 문제인가? 싶었는데 생각해보면 크게 복잡하지 않음. 인접행렬 이용한다 생각하면 단순했음.
2. 만약 (a1, a2)를 출력했다면 (a1, a2)는 다시 출력하면 안됨. 인접행렬에서 연결 여/부를 부로 바꿔주면 됨.
3. 다음 것을 출력할 때 사전순으로 가장 빠른 것을 출력하려면? 1부터 걍 완탐하면서 인접행렬이 연결되어있다면 출력해주면 됨. 그리고 출력한 점을 다음 점으로 업데이트
4. 그런데 3번까지만 해주면 아래와 같은 오류 생김

   N = 5
   a1 -> a2 -> a3 -> a1 -> a4 -> a2 -> a5 -> a1
   // a5-a1의 연결선은 남아있지만, a1의 다음 연결선이 남아있지 않음
   // nC2만큼 진행이 안되고 중간에 끊긴다.

   그래서 (ai, aj)의 연결선이 남아있다면, aj의 연결선이 하나라도 남아있는지, 즉 진행이 가능한지 확인을 해줘야함.

---

Pseudo code

int get_next(i) {
    for (j = 1~n)
        if (인접행렬에 [i, j] 없으면)
            continue
        if (j에 남은 연결선 수가 1개)
            continue
        인접행렬[i, j] = 0
        인접행렬[j, i] = 0
        남은연결선[i]--
        남은연결선[j]--
        return j;
}
현재 = get_next(현재)

---

Source code

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

const int N = 510;
int n;
int a[N][N], b[N];
int print(int i) {
    for (int j=1; j<=n; j++)
        if (a[i][j] && 1<b[j]) {
            a[i][j] = 0;
            a[j][i] = 0;
            b[i]--;
            b[j]--;
            return j;
        }
    return -1;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++)
            a[i][j] = 1;
        a[i][i] = 0;
        b[i] = n-1;
    }

    int cnt = n*(n-1)/2;
    int s = 1;
    while (cnt--) {
        printf("a%d ", s);
        s = print(s);
    }
    printf("a%d ", 1);
}