99클럽 코테 스터디 25일차 TIL + [프로그래머스] 순위 두 가지 풀이 ✨

1. 문제 설명

문제 링크

 

2. 접근 방식

KEY WORD: BFS

생각 해야할 점: 하나의 정점이 자신의 위치를 안다는 것은 단방향 그래프에서 해당 정짐이 다른 모든 정점들과 서열를 가진다는 것이다. 이 때, 해당 서열은 간접적으로 파악이 되도 된다.

간접적으로 파악된다는 것은 무슨 뜻인가?

해당 그림은, 문제에서 예시로 주어진, 정점들간의 관계이다. 문제에서는 2번이 1,4,3번에게 패하고, 5번에게 이겼음으로 4등이라고 했다. 5번은 그 2번에게 졌음으로, 1,3,4번에게도 간접적으로 진 것이다. 따라서 2, 5번은 모든 정점에 대해서 서열을 가진다.

(1) 단 방향 그래프를 두 개 만들기

첫 번째 방법은 단 방향 그래프 2개 만들기 이다.
우리의 핵심은, 현재 조회 중인 정점이 간접적으로라도, 모든 정점과 서열을 가지는가? 를 파악하는 것이다. 하지만, 문제에서 주어진 입력은 승패로 서열이 가려진, 단방향 그래프이기 때문에, 자신이 졌던 사람에게는 접근할 수 있지만, 자신이 이겼던 사람에게는 접근하기 힘들다.

그렇다고 해서, 양방향 그래프로 입력 값을 표현하는 순간, 승 패 관계를 알 수가 없어서, 답을 구할 수 없게 된다. 따라서 그래프를 두개로 나눈다. 하나는 이긴 사람을 가리키는 그래프이고, 다른 하나는 진 사람을 가리키는 그래프이다.

모든 정점에 대해서 두 개의 그래프에 대해 BFS를 진행한다. 현재 조회 중인 정점을 A라고 하자. 이때 A에서 두 개의 BFS를 통해 접근한 정점의 수가 n-1 (자신을 제외한 모든 정점)이면, A는 모든 정점들과 서열을 가짐으로, 순위가 있다고 볼 수 있다.

위의 예시에서 2는 왼쪽 그래프에서 3개의 정점을 만나고, 오른쪽 그래프에서 1개의 정점을 만나 나머지 4개를 모두 만난다.
5는 왼쪽 정점에서 4개, 오른쪽 정점에서 0개를 만나, 모든 정점과 서열을 가지고 있다. 그래서 순위를 알 수 있는 정점이 2개가 되어, 답이 2가 된다.

(2) 정점간의 비교 횟수 세기

1번의 논리와 맞닿아 있다. 어떤 정점 A가 다른 모든 정점과 서열을 가진다는 소리는, 정점간의 승패 비교횟수가 n-1이라는 소리이다.

 

1.위의 예시에 나왔던 그래프 중 왼쪽 그래프만 사용한다.

 

 2. 각 정점의 비교 횟수를 세는 배열 (compareCnt)를 만든다. 해당 배열은 정점 간의 비교를 하면, 비교된 정점 두 개의 카운트를 올려준다. 예를 들어 5번에서 BFS를 돌면 5번은 3번에 접근이 가능하다. 그러면, compareCnt[5]와 compareCnt[3]을 모두 +1씩 올려준다.
위의 그래프에서 각 정점마다 BFS를 돌며, 비교 횟수를 세는 배열을 계산하면 다음과 같다.

3.자신을 제외한 모든 정점과 비교하면, n-1번의 비교를 해야한다. 따라서 해당 문제의 답은 정점 2와 정점 5가 나오므로 답은 2 이다.

3. 코드 분석

(1)의 구현 코드

import java.io.*;
import java.util.*;

class Solution {
    static int N;
    static ArrayList<Integer> [] lose;
    static ArrayList<Integer> [] win;
    static int ans = 0;

    public int solution(int n, int[][] results) {
        N    = n;
        lose = new ArrayList [n+1];
        win  = new ArrayList [n+1];

        for(int i = 1; i <= n; i ++){
            lose[i] = new ArrayList<>();
            win[i]  = new ArrayList<>();
        }

        for(int i = 0; i < results.length; i++){
            int winner = results[i][0];
            int loser  = results[i][1];
            lose[loser].add(winner);
            win[winner].add(loser);
        }

        for(int i = 1; i<= n; i++){
            int cnt = 0;
            cnt += bfs(true, i);
            cnt += bfs(false, i);
            if (cnt == n-1) ans++;
        }

        return ans;

    }

    public int bfs(boolean isWinner, int now) {
        ArrayList<Integer> [] list =  isWinner? win : lose; // 현재 사용 중인 그래프 
        ArrayDeque<Integer> aq1 = new ArrayDeque<>();       // BFS 용 queue
        boolean [] isVisited = new boolean[N+1];            // 방문 배열
        int cnt = 0;                                        // 승패가 확인된 개수
        aq1.add(now);
        isVisited[now] = true; 

        while(!aq1.isEmpty()){
            int cur = aq1.poll();

            for(int i = 0; i<list[cur].size(); i ++) {
                int next = list[cur].get(i);
                if(!isVisited[next]){
                    isVisited[next] = true; 
                    cnt++;
                    aq1.add(next);
                }
            }
        }
        return cnt;        
    }
}

(2)의 구현 코드

import java.io.*;
import java.util.*;

/*  문제 설명
     *  순위를 비교함 
     *  승패를 1대1 비교하는데, 1:N으로 전부 다 한 것 아님. 예를 들어 A,B,C,D가 있으면 A,B 승패 비교, BC비교 CD비교했으면 A는 C나 B와 비교를 안한것임
     *  따라서 누구는 승패 비교하는 거 보고 자기가 몇 번째 순서인지 아는데, 누구는 모른다. 
     *  자기가 몇 번째 순서인지 아는 복서의 수를 구하라
     * */

    /*  문제 풀이   */
    // 1. 단방향 그래프를 그린다.
    // 2. 모든 정점에서 출발하여 bfs를 돌린다. 
    // 3. 정점 비교 횟수 배열을 만들고, bfs를 돌려서 특정 정점에 방문했을 경우, 출발 정점과 비교 정점을 cnt+1씩 올린다.  
    //      bfs를 타고 도달할 수 있는 정점은, 인접하지 않아도 서로 간접적으로 비교가 된다는 소리이기 때문이다.
    // 4. 모든 정점에 대한 bfs를 마치고, 정점 A의 방문 횟수가 정점의 갯수와 일치하면, 해당 정점은 자신의 순위를 아는 녀석이다. 이 수를 센다.

class Solution {
    static int N;
    static ArrayList<Integer> [] graph;
    static int [] compareCnt;
    static int ans = 0;

    public int solution(int n, int[][] results) {
        N    = n;
        graph  = new ArrayList [n+1];
        compareCnt = new int [n+1];

        for(int i = 1; i <= n; i ++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < results.length; i++){
            int winner = results[i][0];
            int loser  = results[i][1];
            graph[loser].add(winner);
        }

        for(int i = 1; i <= n; i++){
            bfs(i);
        }

        for(int i = 1; i <= n; i++){
            if(compareCnt[i] == n-1) ans++;
        }
        return ans;
    }

    public void bfs(int now) {
        ArrayDeque<Integer> aq1 = new ArrayDeque<>();
        boolean [] isVisited = new boolean[N+1]; 
        isVisited[now] = true;
        aq1.add(now);

        while(!aq1.isEmpty()){
            int cur = aq1.poll();
            for(int i = 0; i < graph[cur].size(); i++){
                int next = graph[cur].get(i);
                if(!isVisited[next]){
                    isVisited[next] = true;
                    aq1.add(next);
                    compareCnt[now]++;
                    compareCnt[next]++;
                }
            }
        }
    }

}

4. 성장 하기

각 답변의 시간 속도를 비교해보겠다.

(1)번의 각 TC 별 속도

(2)번의 각 TC별 속도

2번이 BFS를 한 번만 돌면 되어서 대체적으로 조금 더 빠른 듯 하다.