[C++] 프로그래머스 Lv3. - 순위 (BFS / 그래프)

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

코딩테스트 연습 - 순위

 

 

문제 설명

n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다.

선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주어질 때 정확하게 순위를 매길 수 있는 선수의 수를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 선수의 수는 1명 이상 100명 이하입니다.
• 경기 결과는 1개 이상 4,500개 이하입니다.
• results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.
• 모든 경기 결과에는 모순이 없습니다.

입출력 예

n	results	return
5	[[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]	2

입출력 예 설명

2번 선수는 [1, 3, 4] 선수에게 패배했고 5번 선수에게 승리했기 때문에 4위입니다.
5번 선수는 4위인 2번 선수에게 패배했기 때문에 5위입니다.

 

 

 

---

 

 

접근 방법

 

자신의 순위를 알려면, 자신을 제외한 n-1명과의 승/패 관계를 모두 알아야한다.

 

vecArrWin[i] 에는 승리한 사람 i를 기준으로 잡고 i에게 진 사람들을 저장했다.

vecArrLose[i]에는 패배한 사람 i를 기준으로 잡고 i를 이긴 사람들을 저장했다.

 

입력 예시를 표현하면 아래와 같다.

vecArrWin[]

index	1	2	3	4	5
vector<int>	{2}	{5}	{2}	{3,2}

 

vecArrLose[]

index	1	2	3	4	5
vector<int>		{4,3,1}	{4}		{2}

 

 

1부터 n까지 BFS를 돌린다.

BFS안에서는 init 노드를 기준으로 init이 이긴 사람들과 Init에게 진 사람들을 카운트한다.

검사할 때는 init 노드에서 시작해서 벡터 배열 안에 있는 노드들을 queue에 넣으면서 탐색을 진행해 나간다.

 

#include <string>
#include <vector>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;

int cntArr[101] = {0};


int BFS(int init, vector<int>* vecArrWin, vector<int>* vecArrLose){
    queue<int> que;
    que.push(init);
    int cnt = 0;
    int visited[101] = {0};
    visited[init] = 1;
    while(!que.empty()){
        
        int startNode = que.front();
        que.pop();
        
        for(int i = 0; i<vecArrWin[startNode].size(); i++){	//i가 승리자 -> i에게 진 사람들 카운트
            if(visited[vecArrWin[startNode][i]] == 0){
                visited[vecArrWin[startNode][i]] = 1;
                que.push(vecArrWin[startNode][i]);
                cnt++;
            }
        }
    }
    memset(visited, 0, sizeof(visited));
    que.push(init);
    visited[init] = 1;
    while(!que.empty()){
        int startNode = que.front();
        que.pop();
        
        for(int i = 0; i<vecArrLose[startNode].size(); i++){ //i가 패배자 -> i가 이긴 사람들 카운트
            if(visited[vecArrLose[startNode][i]] == 0){
                visited[vecArrLose[startNode][i]] = 1;
                que.push(vecArrLose[startNode][i]);
                cnt++;
            }
        }
    }
    cout << endl;
    return cnt;
    
}



int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<int> vecArrWin[101];
    vector<int> vecArrLose[101];
    
    int winner, loser;
    for(int i = 0; i<results.size(); i++){
        winner = results[i][0];
        loser = results[i][1];
        
        vecArrWin[winner].push_back(loser);
        vecArrLose[loser].push_back(winner);
    }
    for(int i = 1; i<=n; i++){
        if(n-1 == BFS(i, vecArrWin, vecArrLose)){		//자신을 제외한 n-1명과 승/패 관계 알아야 함
            answer++;
        }
    }
    return answer;
}