99클럽 코테 스터디 25일차 TIL, 프로그래머스 / 순위

https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=cpp#

프로그래머스

 

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;

int N;
vector<vector<int>> wins;
vector<vector<int>> loses;
vector<int> answers;
vector<bool> visit;

void dfs(bool win, set<int>& acc, int curN)
{
    visit[curN] = true;
    
    if (win)
    {
        // curN '가' 이긴 애들
        for (int w : wins[curN])
        {
            if (visit[w]) continue;
            acc.insert(w);
            dfs(win, acc, w);
        }
    }
    else
    {
        // curN '을' 이긴 애들
        for (int l : loses[curN])
        {
            if (visit[l]) continue;
            acc.insert(l);
            dfs(win, acc, l);
        }
    }
}

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    vector<int> fixed;

    N = n;
    visit.resize(n + 1);
    wins.resize(n + 1, vector<int>());
    loses.resize(n + 1, vector<int>());
    
    for (const vector<int>& result : results)
    {
        int win = result[0];
        int lose = result[1];
        wins[win].push_back(lose);
        loses[lose].push_back(win);
    }
    
    for (int i = 1; i < n + 1; ++i)
    {
        for (int s = 0; s < n + 1; ++s) visit[s] = false;
        set<int> acc;
        acc.insert(i);
        dfs(true, acc, i);
        dfs(false, acc, i);
        
        if (acc.size() == n)
            answer += 1;
    }
    
    // 일단 dfs 로 풀면서, 이긴 애들이 총 몇명인지를 다 구해본다
    // ex) 4 -> 3,2,5 (총 3명)
    // ex) 3 -> 2,5 (2명)
    // ex) 2 -> 5(1명)
    // ex) 1 -> 2(1명)
    // 아니면 모두 일렬로 세워보나 ?
    // 아니면 win, lose 모두 dfs 돌려봐서, 5개면 되는 거 아닌가 ?
    // () 4 (3 2 5)
    // (4) 3 (2 5)
    // (4, 3, 1) 2 (5)
    // (1 4 3 2) 5 -
    
    // 1 (2,3,4)
    // (1) 2 (3)
    // (2) 3
    // (1) 4
    
    return answer;
}