728x90
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
boolean[][] graph = new boolean[n][n];
// graph 인접배열 형태 초기화
for (int[] result : results) {
int win = result[0] - 1;
int lose = result[1] - 1;
graph[win][lose] = true;
}
int count = 0;
for (int p = 0; p < n; p++) {
// node별로 앞뒤로 이어진 edge체크
int lose = countBehind(p, graph, new boolean[n]) - 1;
int win = countFront(p, graph, new boolean[n]) - 1;
// 앞뒤로 이어진 edge의 총합이 n과 일치하면 count
if (lose + win + 1 == n) {
count += 1;
}
}
return count;
}
// node의 뒤를 따라간다 (= 패배한 경기)
public int countBehind(int node, boolean[][] graph, boolean[] visited) {
int count = 1;
for (int i = 0; i < graph.length; i++) {
if (!graph[i][node] || visited[i]) {
continue;
}
visited[i] = true;
count += countBehind(i, graph, visited);
}
return count;
}
// node의 앞으로 간다 (= 승리한 경기)
public int countFront(int node, boolean[][] graph, boolean[] visited) {
int count = 1;
for (int i = 0; i < graph[node].length; i++) {
if (!graph[node][i] || visited[i]) {
continue;
}
visited[i] = true;
count += countFront(i, graph, visited);
}
return count;
}
}
