import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main1325 {
public static ArrayList<ArrayList<Integer>> com;
public static boolean[] check;
public static int N,M;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //컴퓨터의 갯수 N
M = Integer.parseInt(st.nextToken()); //신뢰하는 관계의 갯수
com = new ArrayList<ArrayList<Integer>>();
for(int i=0; i<N+1; i++) {
com.add(new ArrayList<Integer>());
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int A = Integer.parseInt(st.nextToken()); //A가 B를 신뢰한다 .
int B = Integer.parseInt(st.nextToken());
com.get(B).add(A);
}
int[] ans = new int[N+1];
int max = -1;
for(int i=1; i<N+1; i++) {
check = new boolean[N+1];
ans[i] = dfs(i);
max = Math.max(ans[i], max);
}
for(int i=1; i<N+1; i++) {
if(max == ans[i]) {
System.out.print(i + " ");
}
}
}
public static int dfs(int here) {
check[here] = true;
int cnt = 1;
for(int i=0; i<com.get(here).size(); i++) {
int there = com.get(here).get(i);
if(check[there]) continue;
cnt+= dfs(there);
}
return cnt;
}
}
자바는 이방식으로 풀면 시간초과가 나온다.
1. cnt를 전역 변수 배열로 만들어서 처리
2. ArrayList<ArrayList<Integer>> com() -> ArrayList<Integer> com[] ( 인접 리스트 형태 변경)
ArrayList<ArrayList> -> ArrayList<int[]> 이게 효율이 더 좋은건지는 모르겠다.
정답 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main1325{
static int N,M;
static ArrayList<Integer> com[];
static boolean check[];
static int cnt[] = new int[10001];
public static void main(String args[]) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
com = new ArrayList[N+1];
for(int i = 1 ; i <= N ; i++){
com[i] = new ArrayList();
}
for(int i = 0 ; i < M ; i++){
st=new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
com[x].add(y);
}
for(int i =1; i<= N ;i++){
check = new boolean[N+1];
dfs(i);
}
int max = 0;
for(int i =1 ; i <= N ; i++){
if(max <cnt[i]){
max = cnt[i];
}
}
for(int i = 1 ; i <= N ; i++){
if(cnt[i]==max){
System.out.print(i+" ");
}
}
}
public static void dfs(int here){
check[here]=true;
for(int there : com[here]){
if(!check[there]){
dfs(there);
cnt[there]++;
}
}
}
}
'알고리즘 & 자료구조 > 백준' 카테고리의 다른 글
백준 1189 (0) | 2022.03.05 |
---|---|
백준 17298_1 (0) | 2022.03.04 |
백준 1068 (0) | 2022.03.02 |
백준 2636 (0) | 2022.03.01 |
백준 14502 (0) | 2022.02.28 |