프로그래머스 - 순위 - 재귀 - Java

1. 문제

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

2. 풀이

"나"를 기준으로 내 앞으로 몇명이 이겼고, 몇명이 졌는지 파악하고

(나를)이긴 사람 수 + (나에게) 진 사람 수 + (나) 1 = (전체)n

if(wins + loses + 1 == n){
    answer++;
}

이 되는지 확인한다.

✨핵심 Point

1. A가 B를 이겼다는 거니까 방향이 있는 정보이다. 따라서 한쪽만 처리.

map[results[i][0]][results[i][1]] = true;

2. countWins를 셀때 초기 count값을 1로 한다. 그런 뒤에 나중에 -1로 빼준다.

int wins = countWin(i, n, new boolean[n+1]) - 1;
int loses = countLose(i, n, new boolean[n+1]) - 1;

3. 재귀를 count += countWin(v, n, visit); 이용해서 앞에 몇명이 이겼는지 구한다.

3. 전체 코드

import java.util.*;

class Solution {
    boolean map[][];
    
    public int solution(int n, int[][] results) {
        int answer = 0;
        
        map = new boolean[n+1][n+1];
        for(int i = 0; i < results.length; i++){
            map[results[i][0]][results[i][1]] = true;
        }
        
        
        for(int i = 1; i <= n; i++){
            int wins = countWin(i, n, new boolean[n+1]) - 1;
            int loses = countLose(i, n, new boolean[n+1]) - 1;
            
            if(wins + loses + 1 == n){
                answer++;
            }
        }
        return answer;
    }
    
    public int countWin(int u, int n, boolean[] visit){
        int count = 1;
        
        for(int v = 1; v <= n; v++){
            if(visit[v] || !map[u][v]) continue;
            visit[v] = true;
            count += countWin(v, n, visit);
        }
        
        return count;
    }
    
    public int countLose(int v, int n, boolean[] visit){
        int count = 1;
        
        for(int u = 1; u <= n; u++){
            if(visit[u] || !map[u][v]) continue;
            visit[u] = true;
            count += countLose(u, n, visit);
        }
        
        return count;
    }
}