Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
Tags
- docker
- draganddrop
- mongoDB
- spread 연산자
- unity
- java
- nodejs
- Camera Zoom
- SDK upgrade
- express
- Unity Editor
- Git
- --watch
- css framework
- Digital Ocean
- Unity IAP
- react
- Camera Movement
- linux
- Packet Network
- Spring Boot
- rpg server
- critical rendering path
- server
- Google Refund
- OverTheWire
- screencapture
- springboot
- Google Developer API
- MySQL
Archives
- Today
- Total
우당탕탕 개발일지
[프로그래머스] Level 3. 순위 본문
https://school.programmers.co.kr/learn/courses/30/lessons/49191
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
플로이드-워셜 알고리즘
승패정보가 전파된다. for문을 3번 사용하여 a -> b를 이기고 b->c 를 이겼을 경우, a->c 를 이겼음 처리를 해준다.
최단거리 찾는 문제에 보통 사용되는데, 핵심은 삼중for문을 사용하는것이다
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<vector<int>> results) {
int answer = 0;
vector<vector<int>> table (n+1, vector<int>(n+1,0)); //0 모름 1 이김 -1 짐
for(int i=0; i<results.size(); i++){
table[results[i][0]][results[i][1]] = 1;
table[results[i][1]][results[i][0]] = -1;
}
// **Floyd-Warshall 알고리즘 적용**
for (int k = 1; k <= n; k++) { // 중간 경유 선수
for (int i = 1; i <= n; i++) { // 출발 선수
for (int j = 1; j <= n; j++) { // 도착 선수
if (table[i][k] == 1 && table[k][j] == 1) {
table[i][j] = 1; // i가 k를 이기고, k가 j를 이기면 i가 j를 이김
table[j][i] = -1; // j는 i에게 패배
}
if (table[i][k] == -1 && table[k][j] == -1) {
table[i][j] = -1; // i가 k에게 지고, k가 j에게 지면 i도 j에게 짐
table[j][i] = 1; // j는 i를 이김
}
}
}
}
for(int player = 1; player <=n ; player++){
answer++;
for(int i=1; i<=n; i++){
if(player != i && table[player][i] == 0){
answer--; break; //결과모름
}
}
}
return answer;
}
'Algorithm(c++) > Level 3' 카테고리의 다른 글
[프로그래머스] Level 3. 합승 택시 요금 (0) | 2025.03.17 |
---|---|
[프로그래머스] Level 3. 파괴되지 않은 건물 (0) | 2025.03.14 |
[프로그래머스] Level 3. 거스름돈 (0) | 2025.03.13 |
[프로그래머스] Level 3. 셔틀버스 (0) | 2025.03.12 |
[프로그래머스] Level 3. 가장 긴 팰린드롬 (0) | 2025.03.10 |