99클럽 코테 스터디 25일차 TIL 순위

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

프로그래머스

 

1.  문제 및 접근

 

 

1~n번까지의 권투선수, 1대1 방식으로 매치 결과를 0,1의 배열로 주어지는데 0이 이긴 선수 1이 진 선수

주어진 매치 결과 순위를 매기려고 하는데 모든 결과가 있지 않아 정확하게 순위를 매길 수 없다

결과만 보고 정확한 순위를 알 수 있는 선수의 수를 return

 

그래프로 방향성을 주고, 정답 리스트를 놓아서  [0,1,2,3,4,~ , n] 의 값중 하나만 있으면 정답으로 처리하자

 

 

제한사항

 

선수의 수는 1명 이상 100명 이하입니다.

경기 결과는 1개 이상 4,500개 이하입니다.

results 배열 각 행 [A, B]는 A 선수가 B 선수를 이겼다는 의미입니다.

모든 경기 결과에는 모순이 없습니다.

 

 

 

 

2. 내 풀이(틀림)

 

고민한 순서대로 나열하겠다.

 

 

 

이긴 사람의 정보를 넣어줄 지 vs 진 사람의 정보를 넣을 지 고민했다

 

그래서

 

 

1. index 별 이긴 사람의 정보를 넣는다.

2. index 별 진 사람의 정보를 넣는다.

3. 양 방향은 아닌 것 같으니 1,2를 같이 적어보자!

 

 

이렇게 두개의 리스트로 둘다 순회하며 돌면 순위가 배열에 여러 값이 저장되지 않는 사람

즉 하나의 값을 가지는 index라면 그 순위를 확정할 수 있을 것 같았다. 

 

나(Index)를 기준으로 이긴 사람의 정보를 가진 list와 진 사람의 정보를 가진 list ,  총 2개

 

 

 

고민하다 보니, 안 풀려서 내 방식의 접근이 위상정렬이라는 키워드를 알 수 있었고, 

 

위상정렬은 진입차수가 0인 것 부터 출발하는데 list를 두개 돌다보면 진입차수가 1위거나 n위거나 판별 후 진입할 수 있을 것만 같았다...

 

고민하다 클럽장님에게 물어보니, 위상정렬은 답을 내기 힘들다는 답변과

 

플로이드-워셜 알고리즘을 말씀해주셨다.

 

 

 

(위상정렬 말고 그냥 DFS로 접근해도 가능하긴 한데 거기로 돌렸음 더 빨리 풀었을 듯..)

 

 

 

 

3.  플로이드-워셜 알고리즘

 

 

 

 

O(n^3)이라 시간 복잡도를 가지며,

 

현재 n이 100명이 들어올 수 있으니  1,000,000의 데이터가 들어올 수 있는데 충분히 가능하다.

작은 그래프만 써야할 듯 싶다

 

 

 

플로이드-워셜 알고리즘의 핵심은

 

 

"거쳐가는 정점을 기준으로 최단 거리를 구하는 것"

 

 

 

 

다익스트라 vs 플로이드-워셜  ?

 

 

다익스트라는 하나의 정점에서 출발했을때 다른 모든 정점으로의 최단거리를 구하는 알고리즘이고,

 

프로이드-워셜은 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘이다.

 

 

 

다익스트라 알고리즘은 음의 가중치는 구하지 못하는데, 프로이드-워셜은 가능

 

더 정확하게 말해서는 음의 가중치를 가지는 간선이 존재해도 구할 수 있다 (사이클의 의미가 아님!)

 

 

 

 

https://olrlobt.tistory.com/43

 

 

 

 

 

 

탐색 방법은 문제와 엮어서 설명하겠다.

 

 

 

 

 

 

4. 풀이

 

 int answer = 0;


    boolean[][] graph = new boolean[n + 1][n + 1];


    
    for (int[] result : results) {
        int win = result[0];
        int lose = result[1];


        graph[win][lose] = true;
    }


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

        }
    }

    for (int i = 1; i <= n; i++) {
        int count = 0;
        for (int j = 1; j <=n ; j++) {

            if (i != j && graph[i][j] || graph[j][i]) {
                count++;
            }
            
        }
        // 자신을 제외한 모든 선수와의 관계가 확인되면 정확한 순위를 판별할 수 있음
        if (count == n - 1) {
            answer++;

    }}


    return answer;
}

 

 

 

 

 

 

주어진 배열의 정보가  [4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 라면

 

 

• 4번 선수가 3번 선수를 이김
• 4번 선수가 2번 선수를 이김
• 3번 선수가 2번 선수를 이김
• 1번 선수가 2번 선수를 이김
• 2번 선수가 5번 선수를 이김

 

 

 

 

1번째 인덱스부터 실제 들어온 배열에서 이긴 사람을 1로 표현해봤다.

(boolean 값으로 했지만, 보여주기 위해)

 

 

 

 

 

 

 

 

 

 

4-1. 플로이드-워셜 알고리즘 판별

 

 

 

제일 중요한 부분인 거쳐가는 정점[i]를 기준으로  실제 [j][k]를 비교한다.

 

 

j값이랑 k 값을 비교

 

 

 

핵심 로직은

 

 

만약 1번의 선수가 2번을 이기고, 2번의 선수가 3번을 이긴다면 ?

 

 

1번의 선수는 3번의 선수를 이긴다고 할 수 있다. 이게 핵심이다. 거쳐가는 정점으로 확인 하는 것

 

 

 

1 <- 2 이고,

2 <- 3 라면

 

1 <- 3 이다.

 

 

뭔가 삼단논법의 느낌이다~!

 

 

 

그래프를 돌며, 위 공식이 만족하는 대로 채우면

 

 

 

이런 식으로 주어지지 않은 5번의 기록이 채워진다.

 

 

 

 

주어진 정보들로 돌면 이렇게 나머지 순위를 유추할 수 있음

 

 

 

알 수 없던 정보들이 플로이드-워셜 알고리즘을 돌면서 2번에게 진 5번의 순위를 파악할 수 있다.

 

 

 

ex) 1,3,4 한테 진 2번을 거점으로 5번을 탐색의 경우 만들어짐 

 

위의 i, j, k 

 

 

 

 

 

 

4-2. 정확한 순위 카운팅

 

 

 

 

먼저 해당 격투선수마다 (i) 수를 세어줄건데,

 

 

1.  자기 자신과의 경기를 포함시키지 않는다.
2.  graph[i][j] or[j][i]의 값이 있다면 count++; (졌거나 or 이겼거나의 기록)

 

 

 

즉 현재 선수가 4-1을 돈 후에 저장된 값이 자기 자신을 제외한 n-1명과의 기록이 남아있다면 (현재는 4명)

자신의 순위는 정확하게 측정할 수 있다.

 

그럴 경우 answer++;

 

 

 

정확하게 순위를 매길 수 있는 선수는 2명이 나온다.

 

 

 

2번과 5번 선수

 

 

 

 

• 2번의 선수는 다른 1,3,4의 선수에게 졌고, 5번에게 이겼다 ->  4위
• 5번의 선수는 2번에게만 졌는데, 2번이 플로이드-워셜 알고리즘에 의해  -> 5위

 

 

 

 

 

5. 마무리

 

 

몰라서 다양한 방법으로 시도했는데.. 오래 걸리네

 

플로이드-워셜 알고리즘을 처음에 어떻게 적용하지 ? 각 노드들의 최소거리로 어떻게 알 수 있냐 ? 했는데

 

 

핵심 키워드를 보고 바로 파악할 수 있게 하자..

 

이해하기 쉽게 삼단논법 알고리즘이라고 불러야겠다.