코딩테스트 고득점 Kit > 그래프
문제풀이 (2022-03-04 FRI 💻)
⭐ 풀이의 핵심
일단 먹이사슬처럼 (?)
- i가 k를 이기고 k가 j를 이기면 i가 j를 이긴다 라고 표시
- 자신을 제외한 n-1명과의 경기 결과 (승패 여부) 를 알 수 있는 선수에 대해서는 n명 중 자신의 위치가 정해지기 때문에 순위를 확정할 수 있다
와 같이 대략적인 원리는 생각했는데 첫 번째 부분을 구현하는 방법이 잘 떠오르지 않았다
그리고 해답은 무려 3중 for문을 사용해야하는 Floyd-Warshall Algorithm이었다!
처음에 3중 for문까지는 생각이 못 미쳤다.. 머쓱..
Floyd-Warshall Algorithm 또한 알고리즘 기말고사 때 열심히 공부했던 부분인데
코테 문제에 활용해본 것은 처음이어서 아래에 간단하게 정리해보았다
➕ 참고 Floyd-Warshall Algorithm
한 정점에서부터 모든 정점으로까지의 최단 경로를 구하는
Single-Source Shortest Paths의 대표 알고리즘이 Dijkstra(다익스트라) 알고리즘이라면
모든 정점에서부터 모든 정점으로까지의 최단 경로를 구하는
All-Pairs Shortest Paths의 대표 알고리즘은 Floyd-Warshall(플로이드와샬) 알고리즘이라고 할 수 있다
cf. 물론, Single-Source Shortest Paths 알고리즘을 정점의 개수만큼 활용 (즉, 모든 정점을 한 번씩 시작 정점으로 설정) 하여 All-Pairs Shortest Paths 문제를 풀 수도 있다
개인적으로 알고리즘 공부할 때는
백 마디 설명보다 수도코드를 보는 게 이해가 쉬울 때가 많아서
알고리즘 수업 교안을 오랜만에 꺼내서 수도코드를 찾아봤다
/* 수도코드 */
FLOYD-WARSHALL(W)
N = W.rows
D(0) = W
for k = 1 to n
let D(k) = (dij(k)) be a new n*n matrix
for i = 1 to n
for j = 1 to n
dij(k) = min (dij(k-1), dik(k-1) + kj(k-1))
return D(n)
👉 dij(k)는 정점 i에서 정점 j로 가는 최단 거리의 weight를 나타내는 행렬이며, 여기서 정점 i에서 정점 j로 갈 때 중간에 거쳐가는 모든 정점은 {1, 2, ... k} 중에 포함되어 있어야 한다
👉 i는 시작 정점, j는 종료 정점, 그리고 k 값은 중간에 거쳐가는 정점 (즉, 사실상 k == i인 경우에는 continue 해줘도 무방) 을 의미한다
👉 즉, i에서 j로 direct로 가는 것보다 i에서 k를 거쳐서 j로 가는 것이 더 가까울 경우 dij의 값을 dik + dkj의 값으로 업데이트 해주는 것이다
🔽 코드 (C++)
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<vector<int>> results) {
int answer = 0;
// a가 b를 이겼으면 isWinner[a][b]에 true 값 저장
vector<vector<bool>> isWinner(n+1, vector<bool>(n+1, false));
int size = results.size();
for (int i=0; i<size; i++) {
isWinner[results[i][0]][results[i][1]] = true;
}
// Floyd-Warshall Algorithm 활용
// i가 k를 이기고 k가 j를 이긴 경우, isWinner[i][j]에도 true 값 저장
for (int k=1; k<n+1; k++) {
for (int i=1; i<n+1; i++) {
for (int j=1; j<n+1; j++) {
if (i == k) { continue; }
if (isWinner[i][k] && isWinner[k][j]) {
isWinner[i][j] = true;
}
}
}
}
// i가 j를 이긴 경우 또는 j가 i를 이긴 경우 cnt 값 증가
// 자신을 제외한 n-1명과의 경기 결과를 알 수 있을 경우 순위 확정 가능
for (int i=1; i<n+1; i++) {
int cnt = 0;
for (int j=1; j<n+1; j++) {
if (isWinner[i][j] || isWinner[j][i]) { cnt++; }
}
if (cnt == n-1) { answer++; }
}
return answer;
}