이 튜토리얼에서는 C++를 사용하여 원형으로 배치된 상자들을 막대로 연결할 수 있는지 확인하는 쿼리 처리 프로그램을 구현하는 방법을 살펴보겠습니다.
문제 정의
1부터 n까지 번호가 매겨진 상자들이 하나의 원을 이루고 있다고 가정해 보겠습니다. 각 쿼리는 두 상자의 번호 i와 j로 주어지며, 우리의 임무는 i번 상자와 j번 상자를 막대(rod)로 연결하는 것이 가능한지 판단하는 것입니다. 단, 새로 설치하는 막대는 이전에 설치된 어떤 막대와도 교차해서는 안 된다는 조건이 있습니다.
접근 방식
핵심 아이디어는 원 위의 두 현(chord)이 교차하는 조건을 배열로 간단히 판정하는 것입니다. 두 막대 (a, b)와 (c, d)가 서로 교차하려면 a < c < b < d 또는 c < a < d < b를 만족해야 합니다. 이 성질을 활용하면 다음과 같이 문제를 해결할 수 있습니다.
- 연결 상태 저장: 크기 n+1의 배열 arr을 0으로 초기화합니다. arr[x] 값이 0이 아니면 x번 상자가 arr[x]번 상자와 이미 연결되어 있다는 의미입니다.
- 번호 정렬: 매 쿼리마다 항상 작은 번호가 앞에 오도록 두 값을 스왑하여 비교 로직을 단순화합니다.
- 즉시 불가 판정: 두 상자 중 하나라도 이미 다른 상자와 연결되어 있거나, 두 번호가 동일하면 연결이 불가능합니다.
- 교차 검사: 새 막대 양 끝점 사이에 위치한 상자들의 기존 연결 정보를 확인하여, 새 막대가 기존 막대를 가로지르는지 검사합니다.
모든 검사를 통과하면 "Possible"을 출력하고 연결 정보를 배열에 기록하며, 하나라도 조건에 걸리면 "Not Possible"을 출력합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 상자들로 원을 만드는 것이 가능한지 확인하는 함수
void isPossible(int n, int q, int queryi[], int queryj[]) {
int arr[50];
for (int i = 0; i <= n; i++)
arr[i] = 0;
for (int k = 0; k < q; k++) {
int check = 0;
if (queryj[k] < queryi[k]) {
int temp = queryi[k];
queryi[k] = queryj[k];
queryj[k] = temp;
}
if (arr[queryi[k]] != 0 || arr[queryj[k]] != 0)
check = 1;
else if (queryi[k] == queryj[k])
check = 1;
else {
for (int i = 1; i < queryi[k]; i++) {
if (arr[i] != 0 && arr[i] < queryj[k] && queryi[k] < arr[i]) {
check = 1;
break;
}
}
if (check == 0) {
for (int i = queryi[k] + 1; i < queryj[k]; i++) {
if (arr[i] != 0 && arr[i] > queryj[k]) {
check = 1;
break;
}
}
}
}
if (check == 0) {
cout << "Possible" << endl;
arr[queryi[k]] = queryj[k];
arr[queryj[k]] = queryi[k];
}
else
cout << "Not Possible" << endl;
}
}
int main() {
int size = 5;
int q = 2;
int queryi[] = { 3, 5 };
int queryj[] = { 1, 4 };
isPossible(size, q, queryi, queryj);
return 0;
}
출력 결과
Possible
Possible
코드 설명
예제에서는 n=5인 원에 대해 두 개의 쿼리를 처리합니다. 첫 번째 쿼리는 3번 상자와 1번 상자를 연결하는 것으로, 아직 설치된 막대가 없으므로 교차 없이 연결할 수 있어 "Possible"이 출력됩니다. 두 번째 쿼리는 5번 상자와 4번 상자를 연결하는데, 두 상자는 인접해 있고 기존 막대 (1, 3)과도 교차하지 않으므로 역시 "Possible"이 출력됩니다.
시간 복잡도
각 쿼리마다 최악의 경우 O(n) 범위의 검사를 수행하므로, q개의 쿼리를 처리하는 전체 시간 복잡도는 O(n × q)입니다. 공간 복잡도는 연결 상태를 저장하는 배열로 인해 O(n)입니다.