[그래프] Level 3 순위

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

코딩테스트 연습 - 순위

 

---

풀이)

 

파이썬과 자바는 각각 다른 방식으로 풀었다

• 파이썬 : set을 사용
• 자바 : 그래프 탐색 사용

 

하지만 둘 다 큰 조건은 같다

해당 선수를 이긴 사람과 진 사람의 합이 n-1과 같으면 그 선수는 순서를 정할 수 있는 것이다!

 

 

 

 

파이썬 코드)

def solution(n, results):
    answer = 0
    win = {}
    lose = {}
    
    for i in range(1, n+1):
        win[i] = set() # 중복 방지를 위해 set 사용
        lose[i] = set()
        
    for result in results:
        win[result[0]].add(result[1]) # 해당 인덱스 선수에게 진 선수 저장
        lose[result[1]].add(result[0]) # 해당 인덱스 선수를 이긴 선수 저장
        
    for i in range(1,n+1):
        for winner in lose[i]:
            win[winner].update(win[i])
        for loser in win[i]:
            lose[loser].update(lose[i])
            
    for i in range(1,n+1):
        if len(win[i]) + len(lose[i]) == n-1 :
            answer += 1
            
    return answer

• 각 인덱스에 해당하는 선수에게 진 선수들을 저장하는 이차원 배열과 이긴 선수들을 저장하는 이차원 배열을 선언한다 -> win, lose
• 그리고 각각을 set으로 초기화 한다 -> 중복 방지
• 그리고 results 배열을 돌면서 각 인덱스 별 배열에 저장한다
• 모든 동작을 다 하고 각 인덱스 별로 이긴 선수와 진 선수 수의 합이 n-1과 같으면 순위 결정이 가능하므로 answer에 추가한다

 

 

 

 

자바 코드)

import java.util.*;

class Solution {
    static boolean[] visited;
    static ArrayList<ArrayList<Integer>> pGraph = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> cGraph = new ArrayList<>();
    static int count1;
    static int count2;
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        for(int i=0;i<=n;i++) {
            pGraph.add(new ArrayList<>());
            cGraph.add(new ArrayList<>());
        }
        
        for(int i=0;i<results.length;i++) {
            pGraph.get(results[i][0]).add(results[i][1]);
            cGraph.get(results[i][1]).add(results[i][0]);
        }
        
        for(int i=1;i<= n;i++) {
            count1=0;
            count2=0;
            visited = new boolean[n+1];
            pDfs(i);
            cDfs(i);
            
            if((count1+count2) == n-1) {
                answer++;
            }
        }
        return answer;
    }
    
    static public void pDfs(int v) {
        visited[v] = true;
        for(int x : pGraph.get(v)) {
            if(!visited[x]) {
                count1++;
                pDfs(x);
            }
        }
    }
    
    static public void cDfs(int v) {
        visited[v] = true;
        for(int x : cGraph.get(v)) {
            if(!visited[x]) {
                count2++;
                cDfs(x);
            }
        }
    }
}

• 그래프 탐색을 사용하여 풀었다
• 부모 노드 개수 + 자식 노드 개수 = n-1 이면 순위 결정 가능하다
• 난 이긴 선수 저장하는 배열과 진 선수 저장하는 배열을 2개로 선언하고 dfs도 두 개로 만들어서 각각 돌았다
• 그리고 그 합이 n-1이면 순위 결정이 가능하니까 answer++ 을 한다