[프로그래머스] Lv.3 순위 (Java)

프로그래머스 - 그래프 - 순위

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

프로그래머스

 

 

💡 아이디어

"정확하게 순위를 매길 수 있는 선수" 란?

• (자신보다 실력이 좋은 사람의 수) + (자신보다 실력이 안 좋은 사람의 수) +자신 = n인 사람을 뜻합니다.

 

입출력 예시를 보면

1은 [1보다 실력↑ => x]+[1보다 실력↓ => 2번]+자신=2로 n과 달라 정확한 순위를 알 수 없습니다.

2는 [2보다 실력↑ => 4,3,1]+[2보다 실력↓ => 5]+자신=5로 n과 같아 4위라는 것을 알 수 있습니다.

3은 [3보다 실력↑ => 4] + [3보다 실력↓ => 2,5(5는 2한테 진다)]+자신=4로 순위를 알 수 없습니다.

4는 [4보다 실력↑ => x] + [4보다 실력↓ => 3,2,5] + 자신 = 4로 순위를 알 수 없습니다.

5는 [5보다 실력↑ => 1,2,3,4] + [5보다 실력↓ => x] +자신 = 5로 순위가 5위라는 것을 알 수 있습니다.

---

📗 풀이과정

1. 내가 이긴 사람과 내가 진 사람을 구분하기 위해 단방향 그래프를 만들어줍니다.

 Map<Integer,ArrayList<Integer>> win = new HashMap<>(); // 내가 이긴 사람
 Map<Integer,ArrayList<Integer>> lose = new HashMap<>();// 내가 진 사람

 

2. 주어진 results배열을 돌면서 내가 이긴 사람은 win에 내가 진 사람은 lose에 저장해 줍니다.

for(int i=1;i<=n;i++){//저장공간 만들기
	win.put(i,new ArrayList<>());
	lose.put(i,new ArrayList<>());
}

for(int i=0;i<results.length;i++){
	win.get(results[i][0]).add(results[i][1]); //이긴사람의 win list에 진사람 추가
	lose.get(results[i][1]).add(results[i][0]);//진사람 lose list에 이긴사람 추가
}

 

3. 1번 사람부터 n번 사람까지 DFS(깊이 우선 탐색)을 돌면서 자신이 무조건 이길 수 있는 상대와 자신이 무조건 질 상대를 탐색합니다.

for(int i=1;i<=n;i++){
	dfs(i,win); // i가 무조건 이길 수 있는 상대 탐색
	dfs(i,lose); // 무조건 질 상대 탐색

4. 모든 상대에게 이기거나 진다면 순위를 매길 수 있다는 것이므로 answer+1해 줍니다.

	if(AllVisited()) answer++;
}

//모든 노드를 방문했는지 확인
boolean AllVisited(){
	boolean b = true;
        
	for(int i=1;i<visited.length;i++){
		if(!visited[i]){
			b=false; break;
		}
	}
	return b;
}

 

5. 1번 사람부터 n번 사람까지 탐색을 끝냈으면 answer를 반환하고 끝냅니다.

---

전체 코드

import java.util.*;
class Solution {
    static Map<Integer,ArrayList<Integer>> win = new HashMap<>(); // 내가 이긴 사람
    static Map<Integer,ArrayList<Integer>> lose = new HashMap<>();// 내가 진 사람
    static boolean[] visited;
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        for(int i=1;i<=n;i++){
            win.put(i,new ArrayList<>());
            lose.put(i,new ArrayList<>());
        }
        for(int i=0;i<results.length;i++){
            win.get(results[i][0]).add(results[i][1]); //이긴사람의 win list에 진사람 추가
            lose.get(results[i][1]).add(results[i][0]);//진사람 lose list에 이긴사람 추가
        }
        
        for(int i=1;i<=n;i++){
            visited = new boolean[n+1];
            dfs(i,win); // i가 무조건 이길 수 있는 상대 탐색
            dfs(i,lose); // 무조건 질 상대 탐색
            
            if(AllVisited()) answer++;
        }
        
        return answer;
    }
    //모든 노드를 방문했는지 확인
    boolean AllVisited(){
        boolean b = true;
        
        for(int i=1;i<visited.length;i++){
            if(!visited[i]){
                b=false; break;
            }
        }
        return b;
    }
    //방문할 수 있는 모든 노드 방문.
    void dfs(int i, Map<Integer,ArrayList<Integer>> DirectedGraph){
        
        visited[i]=true;
        
        for(int j : DirectedGraph.get(i))
            if(!visited[j]) dfs(j, DirectedGraph);
    }
}