[프로그래머스] 코딩테스트 연습 - 그래프 Level 3 순위
Solution.java
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
ArrayList<Integer>[] parent = new ArrayList[n];
ArrayList<Integer>[] child = new ArrayList[n];
for (int i = 0; i < n; i++) {
parent[i] = new ArrayList<>();
child[i] = new ArrayList<>();
}
for (int[] result : results) {
parent[result[1] - 1].add(result[0] - 1);
child[result[0] - 1].add(result[1] - 1);
}
for (int i = 0; i < n; i++) {
boolean[] visited = new boolean[n];
int p = dfs(i, parent, visited);
int c = dfs(i, child, visited);
if (p + c == n - 1) answer++;
}
return answer;
}
int dfs(int player, ArrayList<Integer>[] arr, boolean[] visited) {
int num = 0;
for (int i : arr[player]) {
if (!visited[i]) {
visited[i] = true;
num++;
num += dfs(i, arr, visited);
}
}
return num;
}
}
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
int answer = 0;
ArrayList<Integer>[] parent = new ArrayList[n];
ArrayList<Integer>[] child = new ArrayList[n];
for (int i = 0; i < n; i++) {
parent[i] = new ArrayList<>();
child[i] = new ArrayList<>();
}
for (int[] result : results) {
parent[result[1] - 1].add(result[0] - 1);
child[result[0] - 1].add(result[1] - 1);
}
for (int i = 0; i < n; i++) {
boolean[] visited = new boolean[n];
int p = dfs(i, parent, visited);
int c = dfs(i, child, visited);
if (p + c == n - 1) answer++;
}
return answer;
}
int dfs(int player, ArrayList<Integer>[] arr, boolean[] visited) {
int num = 0;
for (int i : arr[player]) {
if (!visited[i]) {
visited[i] = true;
num++;
num += dfs(i, arr, visited);
}
}
return num;
}
}
문제를 보고 위상정렬 알고리즘을 사용하여 풀면 되겠다는 생각이 들었지만
위상정렬 알고리즘이 생각나지않아 풀지 못했다..
위상정렬 알고리즘을 공부한 후 다시 도전해봐야겠다.
위상정렬 알고리즘 문제가 아니었다..
단순히 그래프를 탐색하는 문제였다.
플로이드-워셜 알고리즘을 사용해 풀어도되지만 나는 그냥 DFS 알고리즘을 이용하여 탐색했다.
DFS 대신 BFS를 사용해도 상관없을것 같다.
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
Author And Source
이 문제에 관하여([프로그래머스] 코딩테스트 연습 - 그래프 Level 3 순위), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@hye07on11/프로그래머스-코딩테스트-연습-그래프-Level-3-순위저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)