문제

https://www.acmicpc.net/problem/10159

풀이

DFS

N개의 물건에 대해 무게를 비교하는 쌍 M개가 주어질 때, i번 물건과 무게를 비교할 수 없는 물건의 개수를 구하는 문제이다. (1 <= i <= N)

자기 자신을 제외한 모든 물건과의 무게 비교가 불가능하다면 답은 N-1개가 될 것이다.

이때, i번 물건보다 무게가 큰 물건의 개수, 무게가 작은 물건의 개수를 알고 있다면, N-1에서 이 두 개의 숫자를 빼서 정답을 구할 수 있다.

i번 물건보다 무게가 크거나 작은 물건의 개수를 구하고, N-1에서 이 값을 빼자!

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 101; 
int N, M; 
int cnt = 0; // i번 물건과 무게를 비교할 수 있는 물건의 개수  
vector<int> bigger[MAX];
vector<int> smaller[MAX];
bool visited[MAX];

void input() {
	cin >> N >> M; 

	for(int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;

		bigger[a].push_back(b);  // a > b 
		smaller[b].push_back(a); // b < a
	}
}

void dfs(vector<int> arr[], int x){
	visited[x] = true;
    
    // x번 노드와 연결된 인접 노드 탐색 
	for(auto y: arr[x]){
		if(!visited[y]){
        	// x번 물건과 무게를 비교할 수 있는 물건 개수 갱신
			cnt++;  
			dfs(arr, y);
		}
	}
}

void initVisitedArray() {
	fill(visited, visited + MAX, false);
}

void solution() {
	// i번 물건과 무게 비교가 불가능한 물건의 개수 출력하기 
	// 각 케이스마다 방문 배열, cnt 변수 초기화 잊지 말기! 
	for(int i = 1; i <= N; i++){
		dfs(bigger, i); 
		initVisitedArray(); 
		
		dfs(smaller, i);
		initVisitedArray(); 
		
		cout << (N - 1) - cnt << "\n"; 
		cnt = 0;
	}
}

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

	input(); 

	solution(); 
	
	return 0; 
}

N: 노드 개수, M: 간선 개수

인접 리스트로 DFS를 구현하는 경우 시간 복잡도는 O(N + M)이므로

위 풀이의 시간복잡도는 O(N * (N + M)) 이라고 할 수 있다. (N은 최대 100, M은 최대 2000)

인접 행렬로 DFS를 구현한다면 시간 복잡도는 O(N^2)이므로

이 문제의 최종 시간복잡도는 O(N^3) 이 될 것이다.

플로이드-워셜

인접 리스트가 아닌 인접 행렬 방식으로 그래프를 구성한다.

그리고 2개의 물건에 대한 대소 관계에 따라

• graph[a][b] = 1 (a > b)
• graph[b][a] = -1 (b < a)

이런 식으로 배열에 값을 저장한다.

그리고 (i, k), (k, j) 간의 대소 관계에 따라 (i, j)의 대소 관계를 갱신하고

최종적으로 N-1에서 대소 관계 비교가 가능한 개수를 제외하여 정답을 구할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> pii;

const int MAX = 101; 
int N, M; 
int graph[MAX][MAX]; 

void input() {
	cin >> N >> M; 

	for(int i = 0; i < M; i++){
		int a, b;
		cin >> a >> b;

		graph[a][b] = 1; 
		graph[b][a] = -1; 
	}
}


void floyd() {
	for(int k = 1; k <= N; k++){
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++){
				// (i, k), (k, j)의 대소 관계가 같다면
				if(graph[i][k] == graph[k][j] && graph[i][k] != 0){
					// (i, j)의 대소 관계 갱신 
					graph[i][j] = graph[i][k]; 
				}
			}
		}
	}
}

void solution() {
	for(int i = 1; i <= N; i++){ 
		int cnt = N - 1; 

		// 대소 비교가 가능한 쌍의 개수만큼 N-1에서 뺀다. 
		for(int j = 1; j <= N; j++){
			if(graph[i][j] != 0) cnt--; 
		}
		
		cout << cnt << "\n"; 
	}
}

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

	input(); 

	floyd(); 

	solution(); 
	
	return 0; 
}

시간복잡도는 O(N^3)인데 N의 최대 크기가 100이므로 시간초과가 발생하지 않는다.

만약 N이 500 이상이라면 1억번 이상의 연산으로 1초가 넘는 시간이 걸려서 타임아웃 판정을 받을 수 있다.