LEVEL 3 : 순위

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

코딩테스트 연습 - 순위

 

• 문제

  • 

    문제

---

풀이

• 플로이드 와샬 문제로 모든 경우의 수를 계산한다.
• 2차원 boolean 형식을 map을 생성한 뒤, 플로이드 와샬 알고리즘을 사용한다.
  • i -> k , k -> j 가 연결되어 있다면 i->j 또한 연결되어 있다.
  • if(map [i][k] && map [k][j]) map [i][j] = true;
• 모든 경우의 수를 다 계산한 뒤,
  • 자기 자신을 제외한 다른 것들의 순위중 계산할 수 없는 게 한 개라도 존재하면 순번을 알 수 없는 노드이다
  • 자기 자신을 제외한 다른 것들의 순위중 계산할 수 없는 게 한 개라도 존재하지 않다면 순번을 알 수 있으므로 answer을 증가시킨다.

•  public static int solution(int n, int[][] results) {
   	int answer = 0;
   	boolean[][] map = new boolean[n][n];
   	for(int i=0;i<results.length;++i) {
        int start = results[i][0] - 1;
        int end = results[i][1] - 1;
        map[start][end] = true; //시작 위치 -> 종료 위치에 있는 것을 방문 표시한다.
   	}
   	//플로이드 와샬 알고리즘
      for(int k=0;k<n;++k) {
      	for(int i=0;i<n;++i) {
      		for(int j=0;j<n;++j) {
       			if(map[i][k] && map[k][j]) { // 만약 i -> k , k -> j로 가는 길이 있다면 i -> j 로 가는 길도 존재
       				map[i][j] = true;
       			}
       		}
       	}
       }
       OUTER:for(int i=0;i<n;++i) {
  		for(int j=0;j<n;++j) {
     			if(i == j) // 자기 자신이 아니고
      			continue;
      		if(map[i][j] == false && map[j][i] == false) // j -> i, i -> j 둘 다 알 수 있는 방법이 없다면 그 노드는 순위를 알수 없다
      			continue OUTER;
           	}
      	answer++;//여기까지 왔다면 순위를 알수 있는 것이므로 answer 증가
      }
      return answer;
  }

•