[프로그래머스]level-3 순위 (플로이드 와샬 알고리즘)
22435 단어 플로이드와샬알고리즘cpp알고리즘프로그래머스cpp
프로그래머스에서 순위 라는 문제를 만났음
플로이드 와샬 알고리즘을 이용하는 문제라고함
플로이드 와샬이 뭔지 알아보고 풀어보기~!
-
다익스트라알고리즘 : 하나의 정점에서 모든 정점으로 가는 최단경로
-
플로이드와샬 : 모든 정점에서 모든 정점으로 가는 최단경로
- 2차원 배열로 값이 저장된다고 생각(다익스트라는 1차원)
- x->y 가는 비용 vs x -> node1 + node1 -> y 합산 비교해서 적은 값 갱신
#include <string>
#include <vector>
using namespace std;
int number = 4;
int INF = 100000000;
//자료 배열 초기화 ( i > j 거리)
int a[4][4] = {
{0, 5, INF, 8},
{7, 0, 9, INF},
{2, INF, 0, 4},
{INF, INF, 3, 0}
};
void floydWarchall() {
//결과 그래프 초기화
int d[number][number];
for(int i = 0; i < number; i++) {
for (int j = 0; j < number; j++) {
d[i][j] = a[i][j];
}
}
//3중포문으로 구현
//k = 거쳐가는 노드
for (int k = 0; k < number; k++) {
//i는 출발노드
for (int i = 0; i < number; i++) {
//j는 도착노드
for (int j = 0; j < number; j++) {
// 갱신
if (d[i][k] + d[k][j] < d[i][j]) {
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
}
이제 프로그래머스 문제에 적용 시켜보자
일단ㄴ
1~5번 노드까지 있다고 보고 자료배열을 만들어보자
- 총 100명 까지 선수가 있을 수 있음
- 승/패 이기 때문에 boolean 배열로 만듦
bool a[101][101];
int solution(int n, vector<vector<int>> results) {
int answer = 0;
for (int i = 0; i < results.size(); i++) {
int x = result[i][0];
int y = result[i][1];
//x 가 y를 이김
a[x][y] = true;
}
return answer;
}
일단 배운걸 그대로 적용해보면
for(int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][k] && a[k][j]) {
//a[i][j] = a[i][k] + a[k][j];
a[i][j] = true;
}
}
}
}
이러한 3중 반복문이 나온다
이제 정답을 찾을 논리를 떠올려보면
a 가 b 를 이기고 b 가 c 를 이겻으면 a 가 c 를 이긴거라 볼수 있고
저 삼중포문을 돌고나면
각 선수마다 나머지 네 선수에게까지 승패여부가 닿는지를 알 수 있을거다
그러면 자신을 제외한 n-1 번의 승패여부가 영향이 닿는지를 체크하면될 거 같다.
이문제에 적용시킬 때는 최솟값을 계산하여 갱신 시키기 보다 건너건너거 영향력이 닿는지 참/거짓 값을 대입하고 + 추가로 인당 n-1의 결과를 갖고 있게 되어야 한다는 것을 파악해야하는 문제였다.
승 / 패 가 중요하지않다 승패 여부의 영향력이 닿아있어야 한다.
- 전체 코드
#include <string>
#include <vector>
using namespace std;
bool a[101][101];
int solution(int n, vector<vector<int>> results) {
int answer = 0;
for (int i = 0; i < results.size(); i++) {
int x = results[i][0];
int y = results[i][1];
//x 가 y를 이김
a[x][y] = true;
}
for(int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][k] && a[k][j]) {
//a[i][j] = a[i][k] + a[k][j];
a[i][j] = true;
}
}
}
}
for (int i = 1; i <= n; i++) {
int count = 0;
for (int j = 1; j <= n; j++) {
if (a[i][j] || a[j][i]) count++;
}
if (count == n - 1) answer++;
}
return answer;
}
Author And Source
이 문제에 관하여([프로그래머스]level-3 순위 (플로이드 와샬 알고리즘)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@isntkyu/프로그래머스level-3-순위-플로이드-와샬-알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)