안녕하세요! 쏘코입니다.
정말 오랜만에 알고리즘 문제를 손에 잡게 되었습니다.
한동안 기술 스택을 쌓는다고 알고리즘에 조금 소홀했는데, 학기가 끝나서 여유가 생긴 만큼 다시 코테 통과를 위한 알고리즘 공부를 열심히 해야겠죠?
하필이면 제가 제일 두려워 하는 그래프 문제가 기다리고 있다는 것이 참 무서웠습니다.
바로 설명으로 들어가시죠!
출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, https://programmers.co.kr/learn/courses/30/lessons/49191
코딩테스트 연습 - 순위
5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2
programmers.co.kr
목차
0. 문제 설명
n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.
선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.
0.0. 제한사항
- 선수의 수는 1명 이상 100명 이하입니다.
- 경기 결과는 1개 이상 4,500개 이하입니다.
- results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
- 모든 경기 결과에는 모순이 없습니다.
0.1. 입출력 예
| n | results | return |
| 5 | [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] | 2 |
0.2. 입출력 예 설명
2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.
1. 풀이 과정
너무 오랜만에 알고리즘 문제를 풀다보니 조금 막막했습니다.
처음에는 Brute Force로 모든 경우의 수를 따져가며 구해야하나, DFS로 각 노드끼리 연결 여부를 확인해야하나 고민했습니다.
그렇게 감을 못잡으면서 질문하기를 봤더니 플로이드와샬 알고리즘을 사용하면 도움이 된다는 말을 듣고 바로 검색했습니다. (쉬운 알고리즘인데 기억을 못함..)
혹시나 모르시는 분을 위해 말씀드리면 플로이드와샬 알고리즘은 for문을 세번이나 돌리는 DP의 탈을 쓴 Brute Force였네요.. (엄밀히 따지면 Brute Force는 아닙니다만.. ㅋㅋㅋㅋㅋㅋㅋㅋ)
플로이드와샬 알고리즘은 극악의 시간복잡도 O(n^3)을 보여주기 때문에 경우의 수가 얼마나 되는 지를 먼저 파악해야 합니다.
선수의 수가 100명 이하, 경기 결과가 4500개 이하.. 이정도면 O(n^3)을 돌려도 100만 번.. 해볼 만 하겠더라구요!
먼저 선수들간의 승패를 담을 versus라는 이차원 행렬을 만듭니다.
이차원 행렬에는 bool값이 들어가게 됩니다.
versus[승리자][패배자] = true
가 되는 것이죠.
이걸 위해서 먼저 versus의 값들을 먼저 모두 false로 초기화합니다.
지금 생각해보니 그냥 0을 넣었어도 됐겠군요..
이렇게 초기화를 하고 나서는 results 이차원 벡터에서 승리자와 패배자를 가져와서 versus에 넣어줍니다.
versus[승리자][패배자] = true
인데, 우리는 n*n 행렬로 만들었기 때문에 인덱스처리를 위해 results의 값에 -1을 해줍니다.
사람은 1부터지만 컴퓨터는 0부터 세잖아요.
이제 플로이드와샬 알고리즘을 실행합니다.
플로이드와샬 알고리즘은 모든 정점에서부터 다른 모든 정점으로의 최단경로를 구할 때 사용합니다.
다익스트라가 출발점이 정해져있다면, 플로이드와샬은 출발점이 정해져있지 않기 때문에 시간이 훨씬 오래 걸리겠죠?
그리고 이 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행합니다.
이게 무슨 이야기인지는 아래에 추가로 설명하겠습니다.
플로이드와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다고 했죠?
이 문제를 예로 들어보겠습니다.
results에 [4,3], [3,2]가 있죠?
이 말은 4 선수는 3 선수를 이기고, 3 선수는 2 선수를 이긴다는 말입니다.
삼단 논법에 의해서 4 선수는 2 선수를 이기겠죠?
삼단 논법에서 중간에 걸친 3 선수가 바로 정점이 됩니다.
그리고 모든 선수가 한 번씩 정점이 되면서 모든 경우의 수를 비교하게 되는 것이죠.
그나마 다행인게 있다면,
일반적인 최단 경로를 구하는 플로이드와샬 알고리즘에서는 [4,2] 경로와 [4,3][3,2] 경로의 비용을 비교하겠지만,
우리는 비교하는 기본값 (여기서는 [4,2])가 무조건 false이기 때문에 대소비교 같은 것을 할 필요가 없습니다.
그냥 [4,3] [3,2]면 [4,2]의 versus값도 true가 되는 것이죠.
위 내용 때문에
if(versus[j][i] == true && versus[i][k] == true) {versus[j][k] == true}
라는 식이 이번 문제의 플로이드와샬 알고리즘의 핵심이 됩니다!!
이렇게 모든 케이스를 비교해서 시합의 결과를 알 수 있는 모든 경우의 수에 대해서 true값이 부여가 되었다면,
한 선수가 모든 선수들에 대해서 이기든 지든 true값을 가진다면 그 선수의 순위를 매길 수 있게 됩니다.
(공동 순위가 나올 수 있지 않냐는 의문이 있을 수 있는데, A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이긴다는 조건 때문에 물고 물리는 관계가 나올 수가 없습니다.)
그래서 한 정점을 기준으로 잡아서 그 정점이 행일 때와 열일 때의 케이스를 모두 고려해서 true가 몇 개인지 확인합니다.
(여기서 true 대신 1로 했으면 그냥 temp += versus[i][j]랑 temp += versus[j][i] 했어도 됐겠다는 생각이 드네요..)
(i=j 인 경우가 2번 연산되지만, 그 경우의 versus는 자기 자신이랑 경기를 할 수는 없으므로 반드시 false이기 때문에 따로 예외처리를 하지 않아도 됩니다.)
이렇게 true의 개수를 모두 더한 값이 n-1이면 answer에 1을 더해줍니다.
모든 정점에 대한 계산이 끝나면 answer를 반환합니다.
2. 소스 코드
#include <string>
#include <vector>
#include <iostream>
using namespace std;
/*
시간 복잡도: O(n^3)
공간 복잡도: O(n^2)
사용한 알고리즘: 플로이드와샬
사용한 자료구조: vector
설명 : 플로이드와샬 알고리즘을 사용한다. -> 선수의 수가 100명 이하이므로 O(n^3)이어도 할 만하다!
순위를 알기 위해서는 모든 선수들과의 비교가 이뤄져야 한다. (플로이드와셜로 모두와 비교)
이 말은 자기보다 순위가 높은 사람의 수와 순위가 낮은 사람의 수의 합이 n-1이 되야 한다.
*/
int solution(int n, vector<vector<int>> results) {
int answer = 0;
bool versus[n][n]; // 결과값을 담은 행렬
for (int i = 0; i < n; ++i) { // 전부 false로 초기화
for (int j = 0; j < n; ++j)
versus[i][j] = false;
}
// results[i][0]이 승리, results[i][1]이 패배
for (int i = 0; i < results.size(); ++i){
versus[results[i][0]-1][results[i][1]-1] = true;
}
// 플로이드와셜 - 예를 들면 1이 기준일 때는 만약 4가 1을 이긴다면, 1이 이기는 2도 4가 이긴다 ([4,1]이고 [1,2]면 [4,2]다)
for (int i = 0; i < n; ++i){ // 거쳐가는 정점
for (int j = 0; j < n; ++j){ // 행
for (int k = 0; k < n; ++k){ // 열
if(versus[j][i] == true && versus[i][k] == true)
versus[j][k] = true;
}
}
}
// 기준값이 행 일때의 true의 개수 + 기준값이 열 일때의 true의 개수 = n-1 이면 순위 확정 가능!
for (int i = 0; i < n; ++i){
int temp = 0;
for (int j = 0; j < n; ++j){ // 어짜피 i와 j와 같은 경우는 무조건 false이므로 중복 계산해도 temp값에 영향이 없다
if (versus[i][j] == true)
++temp;
if (versus[j][i] == true)
++temp;
}
if (temp == n-1)
++answer;
}
return answer;
}
3. 후기
네.. 제 부족함을 잘 깨달았습니다.
고득점 KIT에서 마지막 남은 문제가 레벨5..라서 굉장히 무섭습니다 ㅋㅋㅋㅋㅋㅋㅋㅋ
그래도 최선을 다해서.. 풀어보도록 하겠습니다!
고득점 KIT의 마지막 문제에서 뵙도록 하겠습니다!
오늘도 읽어주셔서 감사합니다 😄😄
최근댓글