[프로그래머스] 순위 - C++

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49191

프로그래머스

 

• 소요 시간 : 1시간
• 난이도 : LV 3

접근 방법

플루이드-와샬 방법을 변형한다.

 

⬇️ 참고 블로그에 자세하게 설명이 되어 있다.

https://dev-musa.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Level-3-%EC%88%9C%EC%9C%84

프로그래머스 Level 3 순위

 

 

1. 먼저 인접행렬을 만들어서 주어진 결과에 따라 이기고 짐을 나타낸다. (이긴다 = 1, 진다 = -1로 표현)

 

ex. 1은 2한테 이긴다. 

adj[1][2] = 1; 
adj[2][1] = -1;

 

2. 내가 이길 수 있는 노드가 누구를 이기는지 보고, 이에 따라 알 수 있는 결과를 인접행렬에 채운다. 

 

ex. 1이 2한테 이기고, 2는 5한테 이긴다 => 1은 5한테 이긴다, 5는 1에게 진다. 

if (adj[1][2] = 1  && adj[2][5] = 1)  {
	adj[1][5] = 1;
    adj[5][1] = -1
}

 

3. 모든 결과를 통해 추가적으로 채운 후, 인접행렬을 봤을 때  나 자신 빼고 승부한 값이 1 혹은 -1이라면 순위를 정할 수 있다고 판별한다.

 

나의 풀이

#include <string>
#include <vector>
#include <iostream>
#include <cstring>

#define MAX 100+4
#define INF 98754321

using namespace std;

int adj[MAX][MAX];

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            adj[i][j] = INF;
        }
    }
    
    for(int i=1; i<=n; i++) {
        adj[i][i] = 0;
    }
    
    for(vector<int> result : results) {
        int winner = result[0], loser = result[1];
        
        adj[winner][loser] = 1; 
        adj[loser][winner] = -1; 
    }

    for(int k=1; k<=n; k++) {
        for(int j=1; j<=n; j++) {
            for(int i=1; i<=n; i++) {
                if (adj[i][k] == 1 && adj[k][j] == 1) {
                    adj[i][j] = 1; 
                    adj[j][i] = -1;
                }
            }
        }
    }
    

    for(int i=1; i<=n; i++) {   
        int cnt = 0;
        for(int j=1; j<=n; j++) {
            if (i != j && adj[i][j] != INF) cnt++;
        }
        
        if (cnt == n-1) answer++;
    }
    
    return answer;
}

정리

3중 반복문에서 k, i, j의 순서에 유의한다.

가장 바깥쪽 for문은 경유할 정점
가운데 for문은 출발 정점
가장 안쪽 for문은 도착 정점 

 

참고

https://school.programmers.co.kr/questions/56931

프로그래머스

 

https://justicehui.github.io/medium-algorithm/2018/03/25/FloydWarshall/
 

[그래프] 플로이드 와샬 알고리즘