유명인(Celebrity) 문제란?
n명의 사람(0부터 n-1까지 번호가 매겨짐)이 있고, 그중 한 명의 유명인이 존재할 수 있다고 가정해 봅시다. 어떤 사람 x가 나머지 모든 n-1명에게 알려져 있으면서, 정작 x 자신은 그들 중 아무도 알지 못한다면 x를 유명인이라고 정의합니다. 우리가 해야 할 일은 이런 유명인이 실제로 누구인지 찾아내거나, 유명인이 존재하지 않는다는 사실을 확인하는 것입니다.
정보를 얻을 수 있는 방법은 오직 하나뿐입니다. 특정 사람 A에게 'B를 아십니까?'라고 물어 A가 B를 아는지 여부만 확인할 수 있습니다. 따라서 최소한의 질문 횟수로 유명인을 찾아내야 합니다.
입력은 리스트의 리스트 형태로 주어지는 graph입니다. graph[i][j] = 1이면 i번째 사람이 j번째 사람을 아는 것이고, 그렇지 않으면 0입니다.
예를 들어 입력이 graph = [[1,1,0],[0,1,0],[1,1,1]]과 같다면,
출력은 1이 됩니다. 0번과 2번 사람은 모두 1번을 알고 있지만, 1번은 아무도 알지 못하기 때문에 1번이 바로 유명인입니다.
알고리즘 접근 방법
스택(Stack)을 활용하면 효율적으로 후보를 좁혀 나갈 수 있습니다. 핵심 아이디어는 간단합니다. 두 사람을 비교했을 때 한쪽이 다른 쪽을 안다면, 아는 쪽은 유명인일 수 없으므로 후보에서 제외하는 것입니다.
해결 단계
- knows(a, b) 함수 정의: graph[a][b]가 참이면 true를 반환합니다.
- 메인 메서드에서 다음을 수행합니다:
- 정수형 스택 st를 하나 선언합니다.
- i := 0부터 i < n까지 반복하면서 각 i를 스택에 삽입합니다.
- 스택의 크기가 1보다 큰 동안 다음을 반복합니다.
- x := 스택의 top 요소를 꺼냅니다(pop).
- y := 스택의 top 요소를 꺼냅니다(pop).
- knows(x, y)가 참이면 → x는 y를 알기 때문에 유명인이 될 수 없습니다. 따라서 y를 다시 스택에 삽입합니다.
- 그렇지 않으면 → x가 y를 모른다는 뜻이므로 y는 유명인이 될 수 없습니다. 따라서 x를 다시 스택에 삽입합니다.
- 반복이 끝나면 스택에 남은 마지막 후보 x를 꺼냅니다.
- i := 0부터 i < n까지 반복하며 최종 검증을 수행합니다.
- i == x라면 해당 반복은 건너뜁니다.
- knows(x, i)가 참이거나 knows(i, x)가 거짓이라면 → 유명인의 조건을 만족하지 않으므로 -1을 반환합니다.
- 모든 검증을 통과하면 x를 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<vector<int>> graph;
public:
Solution(vector<vector<int>> &graph){
this->graph = graph;
}
bool knows(int a, int b){
return graph[a][b];
}
int findCelebrity(int n) {
stack<int> st;
for (int i = 0; i < n; i++) {
st.push(i);
}
while (st.size() > 1) {
int x = st.top();
st.pop();
int y = st.top();
st.pop();
if (knows(x, y)) {
st.push(y);
}
else {
st.push(x);
}
}
int x = st.top();
for (int i = 0; i < n; i++) {
if (i == x)
continue;
if (knows(x, i) || !knows(i, x)) {
return -1;
}
}
return x;
}
};
int main(){
vector<vector<int>> v = {{1,1,0},{0,1,0},{1,1,1}};
Solution ob(v);
cout << (ob.findCelebrity(3));
}
입력
{{1,1,0},{0,1,0},{1,1,1}}
3
출력
1
복잡도 분석
후보를 추리는 단계에서는 비교할 때마다 한 명씩 제외되므로 n-1번의 질문이 발생합니다. 이후 최종 검증 단계에서는 최대 2(n-1)번의 추가 질문이 필요합니다. 따라서 전체 시간 복잡도는 O(n)이며, 공간 복잡도 역시 스택 사용으로 인해 O(n)입니다. 모든 관계를 일일이 확인하는 O(n²) 방식보다 훨씬 효율적인 접근법입니다.