순위 프로그래머스(lv3) 49191

 

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

 

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

//visited 값을 들고와서 대입 ,false가 1개여야함 
class Solution {
    static boolean[][] result ;
    static int answer;
    static boolean[][] visited ;
    
    
    public int solution(int n, int[][] results) {
    visited = new boolean[n][n];
    
    //visited 배열 초기화
    for(int i = 0 ; i < results.length; i++) {
    	visited[results[i][0]-1][results[i][1]-1] = true;
    }
    
    //순번을 어떻게 연결 시킬까?
    for(int i = 0 ; i < n ; i ++) {
    	for(int j = 0 ; j < n ; j++) {
    		for(int k = 0 ; k < n ; k++) {
    			if(visited[j][i] && visited[i][k]) {
    				visited[j][k]=true;
    			}
    		}
    	}
    }
    
    //둘 중 한명의 경기결과라도 가지고 있으면 경기를 한거다.
    for(int i = 0 ; i < n ;i++) {
    	int cnt = 0;
    	for(int j = 0 ; j < n ; j++) {
    		if(visited[i][j] || visited[j][i]) {
    			cnt++;
    		}
    		
    	}
        if(cnt == n-1) {
    			answer++;
    		}
    }
        return answer;
    }
}

 

이 문제에서 힘들었던 점은

1. 순위의 중간을 어떻게 연결시키겠는가?

였다.

 

이 과정을 도출하기 전에

 

bfs,백트래킹으로 접근을 시도했지만 실패했고 (배열 앞의 선수들의 순번이 갱신되지않았다)

 

 

 

2차원 배열로 [선수][경기결과] 를 차례대로  넣은 배열을 만들어서

선수당 false가 1개여서  경기결과가 나오는경우  answer를 1씩 더해주는 식으로 생각했다.

 

//순번을 어떻게 연결시킬까? 

에서 처음엔이렇게 시작했다. visited에서 i , j 의위치가 바뀜

 

정답이 반 만 맞아서 곰곰이 생각해봤더니

i에서 k 로 j를 거쳐 간다는 거였는데 

 

i는 가장 바뀌지 않는 가장 큰틀이 문제였던 것같다

 

 그 이유가 j가 i보다 자주바뀌기 때문에 중간에 값이 의도하지 않게 변하여서 

    

이 식이 맞았다는 결론이 도출되었다.

 

 

이 식은 결국 플로이드 -워셜 식이라는 알고리즘이었고,

알고리즘을 모른 채로 풀다보니 너무 돌아갔고 좀 더 알고리즘 공부를 해야겠다는 생각을 했다.