[Java]프로그래머스- 순위(DFS, 깊이 우선 탐색)

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

프로그래머스

 

< 문제 요약 >

results에 주어진 권투 대회의 일부의 경기 결과를 통하여 정확하게 순위를 매길 수 있는 선수 찾기.  전체의 결과가 아니라 일부로 선수들의 순위를 매기기.

 

 

Input값: results [][]:  [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

승자	패자
4	3
4	2
3	2
1	2
2	5

 

---

사용한 알고리즘

 

깊이 우선 탐색(DFS)

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법.

 

출처:&amp;amp;nbsp;https://velog.io/@chayezo/%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89DFS-Depth-First-Search

- 보통 Stack이나 재귀로 구현(재귀로 많이 구현)

- 주의할 점: 방문 확인을 하여 무한 루프 주의

---

풀이

 

Input값: results[][]:  [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]]

승자	패자
4	3
4	2
3	2
1	2
2	5

 

1) 승자 ArrayList []배열에 results [][]를 읽어서 넣는다

= winner[i]= {i한테 진 패자들} 

-> 일부의 결과만 들어간다.

winner [1]= {2}

winner [2]={5}

winner [3]={2}

winner [4]={3, 2}

winner [5]={}

 
 

2) 재귀 >< 

winner [i]= { j } ,  winner [j]= {...}

선수 i의 패자인 선수 j한테 진 사람들은 선수 i한테도 진다!

그리하여 재귀로 i의 패자들의 winner [j]를 돌며 winner [i]에 넣어준다.

 

  // DFS를 사용하여 승자에 패자 리스트 전부 채워주기
        for(int i=1; i<=n; i++){
            visited=new boolean[n+1];
            winner[i]=DFS(i,new ArrayList<Integer>());
        }
        

public static ArrayList<Integer> DFS(int i, ArrayList<Integer> li){
        // 위너의 패자를 탐색하며 그 패자의 패자들을 넣어주기 위한 DFS
        for(int loser:winner[i]){

            if(!visited[loser]){
                visited[loser]=true;
                li.add(loser);
                DFS(loser,li);
            }
        }
        return li;
    }

 
 
 

3) 정확한 순위를 매기기 위해서는

이긴 수 + 진 수

= 전체 선수(n) -자기 자신(1)

= n-1

 

1.

이긴 수

= winner [i]의 패자 수

= winner[i]의 length

 

2.

진 수=

 winner [a]={ i , b , c}

winner 배열에 패자에 포함될 때 +1 

 
 

선수들의 이긴 수와 진 수의 합이 n-1인 사람 찾기

// winner[i]에는 각 선수별 탐색할 수 있는 모든 패자들을 넣어주었다.
        // 정확하게 순위를 매길 수 있는 선수는 이긴 수 + 진 수 = n-1여야 한다.
        int [] cnt=new int[n+1];

        for(int i=1; i<=n; i++){
            // i 이긴 수 체크
            cnt[i]+=winner[i].size(); // i 의 패자리스트의 개수 더해주기
            // i의 패자리스트에 값-> j의 진 수 체크

            for(int j:winner[i]){
                cnt[j]++; // j는 i에게 졌으므로 cnt[j]++
            }
        }

        // cnt[i]=n-1일 때 정확하게 순위 매길 수 있다.
        for(int sum:cnt){
            if(sum==(n-1))answer++;
        }