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

문제 링크: programmers.co.kr/learn/courses/30/lessons/49191

코딩테스트 연습 - 순위

0. 유사 문제

www.acmicpc.net/problem/16940

16940번: BFS 스페셜 저지

 

1. 주의할 점

- 순위가 정해져 있는 조건은?

 

2. 구현

- 순위가 정해져 있는 경우: 전체 N명에서 현재 위치에서 자기 앞에 A명, 자기 뒤에 B명이 있다면 A+B = N-1인 경우다(자기자신 제외)

- 위의 경우를 어떻게 찾을 것인가? → 플로이드 와샬(다익스트라를 사용해도 되지만 N번의 다익스트라보단 플로이드 와샬이 나을거라고 판단했다). 단, 이때는 간선의 가중치가 없으므로 배열의 메모리를 최대한 줄이기 위해 Boolean을 사용한다

- 플로이드 와샬 알고리즘을 사용한 후, canReach와 canBeReached의 수를 구하고 둘의 합이 N-1이면 Answer++를 수행한다

#include <string>
#include <vector>
#include <iostream>
using namespace std;
bool arr[101][101]={false,};

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    for(int i=0;i<results.size();i++){
        int win = results[i][0];
        int lose = results[i][1];
        arr[win][lose]=true;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=0;j<=n;j++)
                if(arr[i][k] && arr[k][j])
                    arr[i][j]=true;
    for(int i=1;i<=n;i++){
        int canReach=0,canBeReached=0;        
        for(int j=1;j<=n;j++){
            if(arr[i][j]) canReach++;    //i->j까지 가능
            if(arr[j][i]) canBeReached++;   //j->i까지 가능
        }
        if(canReach+canBeReached==n-1)
            answer++;
    }      
    return answer;
}