47번 : 효율적으로 해킹하기

시간 제한 : 5초, 난이도 : 실버1, 백준 : 1325번

역방향으로 푸는게 맞을듯..? → 성능적으로
BFS 문제 → ArrayDeque 사용하기 (LinkedList보다 성능 좋음)
역방향, 순방향 둘 다 되긴 된다. → 왜 되는지 모르겠음
bfs마다 새롭게 visited 배열을 만들어주는 것도 꽤 시간이 걸리는 작업입니다.

visited 배열을 int[]로 바꾸면 새로 만들 필요가 없어집니다.

어떤 정점을 방문했을 때는 visited에 num을 넣어줍니다.

아직 방문하지 않은 정점들은 visited에 num보다 작은 숫자가 들어 있으므로 bfs를 문제 없이 수행할 수 있습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Practice47 {
	static int N, M;
	static boolean visited[];
	static int answer[];
	static ArrayList<Integer> A[];

	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());
		A = new ArrayList[N + 1];
		answer = new int[N + 1];
		for(int i = 1; i <= N; i++) {
			A[i] = new ArrayList<>();
		}
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int S = Integer.parseInt(st.nextToken());
			int E = Integer.parseInt(st.nextToken());
			A[S].add(E); // 여기 A[E].add(S);
		} // 정방향일때 돌아갑니다. 역방향일때 안 돌아간다.
		for(int i = 1; i <= N; i++) {
			visited = new boolean[N + 1]; 
			BFS(i);
		}
		int maxVal = 0;
		for(int i = 1; i <= N; i++) {
			maxVal = Math.max(maxVal,  answer[i]);
		}
		for(int i = 1; i <= N; i++) {
			if(answer[i] == maxVal)
				System.out.print(i + " ");
		}		
		
	}

	public static void BFS(int index) {
		Queue<Integer> queue = new LinkedList<Integer>(); //ArrayDeque으로 변경하면 돌아감
		queue.add(index);
		visited[index] = true;
		while(!queue.isEmpty()) {
			int now_Node = queue.poll();
			for(int i : A[now_Node]) {
				if(visited[i] == false) {
					visited[i] = true;
					answer[i]++;
					queue.add(i);
				}
			}
		}
	}
}

아래도 시간 초과


import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Practice47 {
	static int N, M;
	static boolean visited[];
	static int answer[];
	static ArrayList<Integer> A[];

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		A = new ArrayList[N + 1];
		
		answer = new int[N + 1];		
		for(int i = 1; i <= N; i++) {
			A[i] = new ArrayList<>();
		}
		for(int i = 0; i < M; i++) {
			int S = sc.nextInt();
			int E = sc.nextInt();
			A[S].add(E);
		}
				
		
		for(int i = 1; i <= N; i++) {
			visited = new boolean[N + 1];
			BFS(i);
		}
		
		int maxVal = 0;
		for(int i = 1; i <= N; i++) {
			maxVal = Math.max(maxVal, answer[i]);
		}
		
		for(int i = 1; i <= N; i++) {
			if(answer[i] == maxVal)
				System.out.print(i + " ");
		}		
		
		sc.close();
	}

	public static void BFS(int index) {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(index);
		visited[index] = true;
		while(!queue.isEmpty()) {
			int now_Node = queue.poll();
			for(int i : A[now_Node]) {
				if(visited[i] == false) {
					visited[i] = true;
					answer[i]++;
					queue.add(i);
				}
			}
		}
	}
}

아래도 시간 초과


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Practice47 {
    static int N, M;
    static ArrayList<Integer>[] graph;
    static int[] dp;
    static boolean[] visited;
    static int max = Integer.MIN_VALUE;

	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());

	        graph = new ArrayList[N + 1];
	        dp = new int[N + 1];

	        for (int i = 1; i <= N; i++) {
	            graph[i] = new ArrayList<>();
	        }

	       
	        for (int i = 0; i < M; i++) {
	            st = new StringTokenizer(br.readLine());
	            int A = Integer.parseInt(st.nextToken());
	            int B = Integer.parseInt(st.nextToken());
	            graph[B].add(A);
	        }

	        for (int i = 1; i <= N; i++) {
	            visited = new boolean[N + 1];
	            dp[i] = dfs(i);
	            max = Math.max(max, dp[i]);
	        }

	        for (int i = 1; i <= N; i++) {
	            if (dp[i] == max) {
	                System.out.print(i + " ");
	            }
	        }
	}

	static int dfs(int node) {
        visited[node] = true;
        int count = 1;

        for (int next : graph[node]) {
            if (!visited[next]) {
                count += dfs(next);
            }
        }

        return count;
    }
}

// DFS로 돌아가는 코드입니다.(여진) 이해 못함.

public class Main {

    static final int N = 10001;
    static int max = 0;

    static List<Integer>[] list = new ArrayList[N];
    static List<Integer> result = new ArrayList<>();
    static boolean[] visit = new boolean[N];
    static int[] connect = new int[N];

    static void DFS(int current){

        visit[current] = true;

        for(int next : list[current])
            if(!visit[next]) {
                connect[next]++;
                DFS(next);
            }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }

        for(int i=1; i<=m; i++){
            st = new StringTokenizer(br.readLine());

            int home = Integer.parseInt(st.nextToken());
            int target = Integer.parseInt(st.nextToken());

            list[home].add(target);
        }

        for(int i=1; i<=n; i++) {
            visit = new boolean[N];
            DFS(i);
        }

        for(int i=1; i<=n; i++)
            if (connect[i] > max) {
                max = connect[i];
                result.clear();
                result.add(i);
            } else if (connect[i] == max)
                result.add(i);

        for(int a:result)
            System.out.print(a + " ");
    }
}

//BFS로 돌아가는 코드~(소망)
import java.io.*;
import java.util.*;

public class Main {
    static int N, M, max = 0;
    static ArrayList<Integer>[] graph;

    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());

        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            graph[b].add(a); 
        }

        int[] result = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            boolean[] visited = new boolean[N + 1];
            Queue<Integer> q = new LinkedList<>();
            q.add(i);
            visited[i] = true;

            int count = 0;

            while (!q.isEmpty()) {
                int cur = q.poll();
                for (int next : graph[cur]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        q.add(next);
                        count++;
                    }
                }
            }

            result[i] = count;
            max = Math.max(max, count);
        }

        for (int i = 1; i <= N; i++) {
            if (result[i] == max) System.out.print(i + " ");
        }
    }
}