(프로그래머스) 순위

문제 링크

• 프로그래머스

요약

• 적용할 수 있는 graph 관련 알고리즘을 생각해 보자.
• 다음에 다시 한번 풀어보기

최종 §

결과

• 이 문제는 Floyd-Warshall 알고리즘을 이용해 모든 인원과 직/간접적으로 대결을 한 선수가 몇명인지 찾으면 된다.
• 그래서 코드는:

#include <string>
#include <vector>
 
using namespace std;
 
#define WIN (1)
#define DONNO (0)
#define LOSE (-1)
 
int solution(int n, vector<vector<int>> results) {
	vector<vector<int>> conn(n, vector<int>(n, DONNO));
	int cnt = 0;
 
	for (auto &res : results) {
		conn[res[0] - 1][res[1] - 1] = WIN;
		conn[res[1] - 1][res[0] - 1] = LOSE;
	}
 
	for (int k = 0; k < n; k++) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i == j) {
					conn[i][j] = WIN;
				} else if (i != k && k != j) {
					if (conn[i][k] == WIN && conn[k][j] == WIN) {
						conn[i][j] = WIN;
					} else if (conn[i][k] == LOSE && conn[k][j] == LOSE) {
						conn[i][j] = LOSE;
					}
				}
			}
		}
	}
 
	for (auto &boxer : conn) {
		bool all = true;
		for (auto res : boxer) {
			if (res == DONNO) {
				all = false;
				break;
			}
		}
		if (all) {
			cnt++;
		}
	}
 
	return cnt;
}

삽질 기록 §

코드

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
#define PACK(i, stage) (((i) << 16) | ((stage) & 0xFFFF))
#define UNPACK_I(pack) (((pack) >> 16) & 0xFFFF)
#define UNPACK_STAGE(pack) ((pack) & 0xFFFF)
 
int solution(int n, vector<vector<int>> results) {
	vector<int> in_degree(n);
	vector<vector<int>> adj(n);
 
	for (auto &res : results) {
		in_degree[res[0] - 1]++;
		adj[res[1] - 1].push_back(res[0] - 1);
	}
 
	queue<int> q;
	for (int i = 0; i < n; i++) {
		if (!in_degree[i]) {
			q.push(PACK(i, 0));
		}
	}
 
	int cur_stage = 0;
	int stage_cnt = 0;
	int cnt = 0;
	while (!q.empty()) {
		int pack = q.front();
		int id = UNPACK_I(pack);
		int stage = UNPACK_STAGE(pack);
		q.pop();
 
		if (cur_stage == stage) {
			stage_cnt++;
		} else {
			cur_stage = stage;
 
			if (stage_cnt == 1) {
				cnt++;
			}
 
			stage_cnt = 1;
		}
 
		for (auto winner : adj[id]) {
			in_degree[winner]--;
 
			if (!in_degree[winner]) {
				q.push(PACK(winner, stage + 1));
			}
		}
	}
 
	if (stage_cnt == 1) {
		cnt++;
	}
 
	return cnt;
}

• 처음에는 Topological Sort 를 사용하는 문젠줄 알았다.
• 하지만 문제에서 주어진 예제만 잘 살펴봐도 그렇게 접근하면 안된다는 것을 알 수 있다.