C++로 세 비행기가 순환적으로 서로를 좋아하는지 확인하는 프로그램

크기가 n인 배열 A가 있다고 가정해 보겠습니다. 지구 위에는 n대의 비행기가 있으며, 각 비행기에는 1부터 n까지 번호가 붙어 있습니다. 번호가 i인 비행기는 비행기 A[i]를 좋아하고, 어떤 비행기도 자기 자신을 좋아하지 않습니다(A[i] ≠ i). 우리가 확인해야 할 것은 p는 q를 좋아하고, q는 r을 좋아하며, r은 다시 p를 좋아하는 순환 관계를 이루는 세 비행기 p, q, r이 존재하는지 여부입니다.

예를 들어 입력이 A = [2, 4, 5, 1, 3]이라면 출력은 True입니다. 비행기 1은 비행기 2를, 비행기 2는 비행기 4를, 비행기 4는 다시 비행기 1을 좋아하기 때문에 [2, 4, 1]이라는 순환 삼중항이 성립하기 때문입니다.

문제 해결 접근 방식

핵심 아이디어는 단순합니다. 각 비행기에서 출발해 '좋아함' 관계를 정확히 세 번 따라간 뒤, 다시 출발점으로 돌아오는지 확인하면 됩니다. 비행기 i에 대해 i → A[i] → A[A[i]] → A[A[A[i]]] 순서로 관계를 추적했을 때 최종 도착 지점이 다시 i라면, 해당 비행기를 포함하는 순환 삼중항이 존재하는 것입니다.

알고리즘 단계

이 문제는 다음 단계를 따라 해결할 수 있습니다.

n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
    if A[A[A[i]]] is same as i, then:
        return true
return false

예제 코드

아래 구현을 통해 더 잘 이해해 보겠습니다.

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

bool solve(vector<int> A) {
    int n = A.size();
    for (int i = 0; i < n; i++) {
        if (A[A[A[i]]] == i) {
            return true;
        }
    }
    return false;
}
int main() {
    vector<int> A = { 2, 4, 5, 1, 3 };
    cout << solve(A) << endl;
}

입력

{ 2, 4, 5, 1, 3 }

출력

1

복잡도 분석

시간 복잡도: 각 비행기마다 상수 번의 배열 참조만 수행하므로 전체 시간 복잡도는 O(n)입니다.
공간 복잡도: 추가적인 자료구조를 사용하지 않으므로 O(1)입니다.