[프로그래머스] 순위 -Java

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

코딩테스트 연습 - 순위

class Solution {
		public int solution(int n, int[][] results) {
			int answer = 0;

			int[][] graph = new int[n + 1][n + 1];

			for (int i = 0; i < results.length; i++) {
				graph[results[i][0]][results[i][1]] = 1;
				graph[results[i][1]][results[i][0]] = -1;
			}

			for (int k = 1; k <= n; k++) { // 들렀다 가는곳
				for (int i = 1; i <= n; i++) { // 시작
					for (int j = 1; j <= n; j++) { // 도착
						if (i == j || graph[i][j] != 0) continue;
						if (graph[i][k] == graph[k][j]) graph[i][j] = graph[i][k];
					}
				}
			}

	 loop: for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (i == j) continue;
					if (graph[i][j] == 0) continue loop;
				}
				answer++;
			}
			return answer;
		}

	}

소요시간 : 20분

 

우선 플로이드 와샬 알고리즘을 사용하였습니다.

N이 100밖에 안되기 때문에 N^3을 사용하더라도 충분하다는 생각으로 하였습니다.

 

2차원 배열에 이긴경기는 1, 진 경기는 -1로 표시하였습니다.

k = 경유지 

i  = 시작지

j =  도착지

로 놓고 풀었습니다!

 

예전에 풀어봤던 문제인데 플로이드 와샬이 가물가물한거 같아서 다시 풀어봤습니다!