[C++][백준 14926] Not Equal

문제

접근 방법

1부터 시작해서 가장 사전 순으로 앞에 오는 곳부터 방문하면 된다.

도중에 이미 방문한 위치를 또 방문하면 안 되므로 bool 벡터로 기록해 주어야 한다.

코드

#include <iostream>
#include <vector>
using namespace std;
vector<vector<bool>> v;
int N;

void solve()
{
    int target = 1;

    v[1][N] = v[N][1] = true;

    for (int i = 1; i <= (N * (N - 1) / 2); ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (j == target || v[target][j])
            {
                continue;
            }

            cout << "a" << target << " ";

            v[target][j] = v[j][target] = true;

            target = j;

            break;
        }
    }

    cout << "a" << target << " ";

    cout << "a1";
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0);

    cin >> N;

    v = vector<vector<bool>>(N + 1, vector<bool>(N + 1));

    solve();

    return 0;
}

풀이

Hint : 한 줄 표기법에 최소로 필요한 "!="의 개수인 C(N, 2)는 Vertex가 N개인 완전 그래프의 Edge의 개수와 동일함을 고려해 보라.

(N * (N - 1) / 2)의 횟수만큼 반복문을 돌면서 수의 위치를 옮겨주면 된다.

예제를 보면 마지막(N)과 1이 연결된 것을 볼 수 있다.

끝에 부분이 아닌 중간 부분에서 N에 위치에 도달한다면 N에 존재하는 수 입장에선 1이 가장 사전 순으로 빠르기에 1로 가게 된다. 그렇게 되면 모든 위치를 돌기 전에 끊겨버리기에 (1에서 다른 길로 가면 모두 중복된 위치가 된다 즉 끊기지는 않지만 (N * (N - 1) / 2)의 회수를 넘는다. 하지만 코드에 중복된 길을 가지 않는 요소를 넣었다면 결국 끊기게 되는 것이다) 정답이 아니다.

미리 이동할 수 없게 방문 처리해 준 뒤 마지막에 출력해 주면 된다.