[고득점Kit][그래프][DFS] 순위 ⭐⭐⭐

[그래프] 순위

난이도 ⭐⭐⭐

문제

풀이 1️⃣ (DFS)

(승리 횟수 + 패배 횟수)가 n - 1이면 그 선수는 정확하게 순위를 매길 수 있는 선수다. 자기 자신을 제외한 n - 1명과의 확실한 순위 비교가 가능한 선수라는 뜻이기 때문에 !

A 가 B 를 이겼고, B 가 C 를 이겼다면 A 는 C 를 이긴적은 없지만 C 보다 더 윗 순위임을 알 수 있다. A 와 C 가 직접적으로 붙었는지 아닌지 알 수는 없더라도 A 는 C 를 이긴 B 를 이겼기 때문에 반드시 C 를 이긴다. 모든 경기 결과에는 모순이 없고 실력이 더 좋은 선수가 항상 이긴다는 가정이 있기 때문에 가능한 발상이다. [A, B]와 [B, C] 데이터로 [A 👉 B 👉 C] 를 만들어내는 것.. DFS가 딱 떠오른다!!! A 가 이긴 상대가 이긴 상대 이런식으로 쭉쭉 깊이 타고 들어가면 될 것이다.

이긴 횟수와 진 횟수를 DFS 방식으로 각각 구할 것이다. 그리고 이 두 횟수를 더했을 때 n - 1이 된다면 그 선수는 확실한 순위를 매길 수 있는 선수다.

• Win [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]
  • 1 선수에서 출발할 때
    • [1, 2] 👉 [2, 5] 즉 1-2-5
    • 선수 1이 확실히 이길 수 있는 선수의 수 = 2, 5 이렇게 2 명 (1가지 경로)
  • 2 선수에서 출발할 때
    • [2, 5] 즉 2-5
    • 선수 2이 확실히 이길 수 있는 선수의 수 = 5 이렇게 1 명 (1가지 경로)
  • 3 선수에서 출발할 때
    • [3, 2] 👉 [2, 5] 즉 3-2-5
    • 선수 3이 확실히 이길 수 있는 선수의 수 = 2, 5 이렇게 2 명 (1가지 경로)
  • 4 선수에서 출발할 때
    • [4, 3] 👉 [3, 2] 즉 4-3-2
    • [4, 2]는 돌지 않는다. 2를 위 경로에서 방문 했었기 때문에. 즉, 2선수는 확실히 4선수가 이길 수 있다는 것이 확인이 됐기 때문에.
    • 선수 4이 확실히 이길 수 있는 선수의 수 = 3, 2 이렇게 2 명 (1가지 경로)
  • 5 선수에서 출발할 때
    • 선수 5이 확실히 이길 수 있는 선수의 수 0 명
• Lose (원소들의 첫번째, 두번째 순서를 바꾼 [[3, 4], [2, 4], [2, 3], [2, 1], [5, 2]] 라고 생각해보자)
  • 1 선수에서 출발할 때
    • 선수 1이 확실히 패배하는 선수의 수 0 명
  • 2 선수에서 출발할 때
    • [2, 4] 즉 2-4
    • [2, 3] 즉 2-3
    • [2, 1] 즉 2-1
    • 선수 2이 확실히 패배하는 선수의 수 = 4, 3, 1 이렇게 3 명 (3가지 경로)
  • 3 선수에서 출발할 때
    • [3, 4] 즉 3-4
    • 선수 3이 확실히 패배하는 선수의 수 = 4 이렇게 1 명 (1가지 경로)
  • 4 선수에서 출발할 때
    • 선수 4이 확실히 패배하는 선수의 수 0 명
  • 5 선수에서 출발할 때
    • [5, 2] 👉 [2, 3] 👉 [3, 4] 즉 5-2-3-4
    • [5, 2] 👉 [2, 1] 👉 즉 5-2-1
    • 선수 5이 확실히 패배하는 선수의 수 = 2, 3, 4, 1 이렇게 4 명 (2가지 경로)

#include <string>
#include <vector>

using namespace std;

int winDFS(vector<vector<int>> results, vector<bool> & visited, int start)
{
    int count = 0;
    visited[start] = true;
    for(int i = 0; i < results.size(); i++)
    {
        if (start == results[i][0] && !visited[results[i][1]])
            count = count + winDFS(results, visited, results[i][1]) + 1;
    }
    return count;
}
                                               
int loseDFS(vector<vector<int>> results, vector<bool> & visited, int start)
{
    int count = 0;
    visited[start] = true;
    for(int i = 0; i < results.size(); i++)
    {
        if (start == results[i][1] && !visited[results[i][0]])
            count = count + loseDFS(results, visited, results[i][0]) + 1;
    }
    return count;
}          

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    for(int i = 1; i <= n; i++)
    {
        vector<bool> winVisited(n + 1);
        vector<bool> loseVisited(n + 1);
        
        int count = winDFS(results, winVisited, i) + loseDFS(results, loseVisited, i);
        
        if (count == n - 1)
            answer++;
    }
    
    return answer;
}

• 각각의 선수들 마다 (for문 1 ~ n 순회) 확실히 이길 수 있는 상대의 수(winDFS) + 붙으면 확실히 지는 상대의 수(loseDFS)를 구한다. 이 두수의 합이 n - 1과 일치하면 이 선수는 확실히 순위를 알 수 있는 선수이므로 answer를 1 증가시킨다.
  • winDFS, loseDFS 방문 체크 벡터를 각각 다른걸로 쓰게 했다. loseDFS를 구할 땐 전부 false로 초기화된 방문 체크 벡터로 시작해야 해서 그냥 두개로 선언했다.
    • 매 for문 반복마다, 즉 선수마다 방문 체크 벡터는 새롭게 선언되고 DFS도 새롭게 진행 된다. 출발지 다른 새로운 경로를 짜는 거라서..

int winDFS(vector<vector<int>> results, vector<bool> & visited, int start)
{
    int count = 0;
    visited[start] = true;
    for(int i = 0; i < results.size(); i++)
    {
        if (start == results[i][0] && !visited[results[i][1]])
            count = count + winDFS(results, visited, results[i][1]) + 1;
    }
    return count;
}

• winDFS 는 results[i][0] 👉 results[i][1] 방향으로의 이동이 진행된다.
  • 깊게 들어가는 조건 👉 results[i][1] 선수 방문 X
• 방문 했던 곳은 다시는 지나치지도 않도록 visited를 reference 로 선언했고 방문 체크를 해제하는 작업도 하지 않는다.
• 각각의 재귀 함수는 count를 리턴한다. 최종적으로 초기 winDFS는 리턴값으로 (각 경로의 길이)들의 합을 받게 될 것이다. 즉, 해당 선수가 확실히 이길 수 있는 선수를 전부 센 값.

  count = count + winDFS(results, visited, results[i][1]) + 1;
  

• 각 단계마다 일단 count는 0으로 초기화 한 상태에서 시작한다. 어차피 리턴되서 상위 호출에서 받는다.

• 각 단계마다 일단 현재의 선수를 방문 체크 해준다.

• loseDFS 는 results[i][1] 👉 results[i][0] 방향으로의 이동이 진행된다.
  • 깊게 들어가는 조건 👉 results[i][0] 선수 방문 X
• 나머지 winDFS와 동일.

풀이 2️⃣ (플로이드 와샬 알고리즘)

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<vector<int>> results) {
    int answer = 0;
    
    vector<vector<bool>> graph(n + 1, vector<bool>(n + 1));
    
    for(int i = 0; i < results.size(); i++)
        graph[results[i][0]][results[i][1]] = true;
    
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (graph[i][k] == true && graph[k][j] == true)
                    graph[i][j] = true;
    
    for(int i = 1; i <= n; i++)
    {
        int count = 0;
        for(int j = 1; j <= n; j++)
            if (graph[i][j] == true || graph[j][i] == true)
                count++;
        if (count == n - 1)
            answer++;
    }
    
    return answer;
}

플로이드 와샬 알고리즘의 자세한 설명은 링크 클릭

    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if (graph[i][k] == true && graph[k][j] == true)
                    graph[i][j] = true;

(i, j) 원소는 i 선수가 j 선수를 이길 수 있느냐에 대한 bool 값이다. i 선수가 n선수를 거쳐서도 j 선수를 이길 수 있는게 확실하다면 원소 값을 True로 설정한다. 확실하지 않다면 기존 값으로 냅둔다. 즉 선수 n을 통해(경유해서) 승리를 확신할 수 있게 된 경우엔 True로 업데이트 해준다. False로 갱신되는 경우는 없음!! (경유 할 수 없으면 False로 바꿔야 하나 하고 혼란스러웠던 적이 있다.)

    for(int i = 1; i <= n; i++)
    {
        int count = 0;
        for(int j = 1; j <= n; j++)
            if (graph[i][j] == true || graph[j][i] == true)
                count++;
        if (count == n - 1)
            answer++;
    }

내가 확실히 승리할 수 있는 선수의 수와 내가 붙으면 확실히 지는 선수의 수를 합한 값이 n - 1 이라면 모두와의 비교가 가능하다는 뜻이니 나는 순위를 확실히 정할 수 있는 사람이므로 이때 answer를 1 증가시킨다. graph[i][j], graph[j][i] 둘 중 하나라도 True 값이라면 동일한 경기에서 누구는 지고 누구는 이겼다는 뜻이니 비교 가능한 경우다.

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기