링크 → https://www.acmicpc.net/problem/1325

• 아영

  • 코드
  • 시간,메모리

• 은영

  • 코드

  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.StringTokenizer;
  
  public class Main {
  
  	static int N,M;
  	static ArrayList<ArrayList<Integer>> map = new ArrayList<>();
      static boolean[] visited;
      static int[] answer;
  	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());
  		
  		for (int i = 0; i <= N; i++) {
              map.add(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());
  
              map.get(a).add(b);
          }
  		answer = new int[N+1];
  		
  		for (int i = 1; i <= N; i++) {
              visited = new boolean[N+1];
              bfs(i);
          }
  		
  		int max = 0;
  
          for (int i = 1; i <=N; i++) {
              max = Math.max(max, answer[i]);
          }
  
          for (int i = 1; i <=N; i++) {
              if(answer[i] == max) {
                  System.out.print(i+" ");
              }
          }
  	}
  	private static void bfs(int i) {
  	    Queue<Integer> queue = new LinkedList<>();
  
          queue.add(i);
          visited[i] = true;
  
          while(!queue.isEmpty()) {
              int temp = queue.remove();
              for(int value : map.get(temp)) {
                  if(!visited[value]) {
                      visited[value] = true;
                      queue.add(value);
                      answer[value]++;
                  }
              }
          }
  	}
  
  }
  

  • 시간,메모리

• 건

  • 코드

  package day_0614;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.LinkedList;
  import java.util.List;
  import java.util.Queue;
  import java.util.StringTokenizer;
  
  public class BOJ1325 {
  	
  	static int n, m;
  	static int[] answer;
  	static List<List<Integer>> map;
  	
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer stk = new StringTokenizer(br.readLine());
  		
  		n = Integer.parseInt(stk.nextToken());
  		m = Integer.parseInt(stk.nextToken());
  		
  		map = new ArrayList<>();
  		for (int i = 0; i <= n; i++) {
  			map.add(new ArrayList<>());
  		}
  		
  		int input1, input2;
  		for (int i = 0; i < m; i++) {
  			stk = new StringTokenizer(br.readLine());
  			input1 = Integer.parseInt(stk.nextToken());
  			input2 = Integer.parseInt(stk.nextToken());
  			map.get(input2).add(input1);
  		}
  		
  		answer = new int[n+1];
  		for (int i = 1; i <= n; i++) {
  			bfs(i);
  		}
  		
  		List<Integer> answerIdx = new ArrayList<>();
  		int max = 0;
  		
  		for (int i = 1; i <= n; i++) {
  			if (max < answer[i]) {
  				max = answer[i];
  				answerIdx.clear();
  				answerIdx.add(i);
  			} else if (max == answer[i]) {
  				answerIdx.add(i);
  			}
  		}
  		
  		for (int i = 0; i < answerIdx.size(); i++) {
  			System.out.print(answerIdx.get(i) + " ");
  		}
  	}
  	
  	static void bfs(int index) {
  		boolean[] visit = new boolean[n+1];
  		Queue<Integer> q = new LinkedList<>();
  		q.add(index);
  		visit[index] = true;
  		int now, count = 0;
  		while(!q.isEmpty()) {
  			now = q.poll();
  			for (int i = 0; i < map.get(now).size(); i++) {
  				if (answer[map.get(now).get(i)] == 0 && !visit[map.get(now).get(i)]) {
  					visit[map.get(now).get(i)] = true;
  					q.add(map.get(now).get(i));
  					count++;
  				} else {
  					count += answer[map.get(now).get(i)];
  				}
  			}
  		}
  		answer[index] = count;
  	}
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ1325 {
      
      private var N = 0
      private var maxCount = -1
      private var hackingCount = [Int]()
      private var links = [[Int]]()
      private var visited = [Bool]()
      
      func solve() {
          readComponents()
          calc()
          printAnswer()
      }
      
      private func readComponents() {
          let temp = readLine()!.split(separator: " ").map{ Int($0)! }
          self.N = temp[0]
          
          hackingCount = .init(repeating: 0, count: N + 1)
          links = .init(repeating: [], count: N + 1)
          
          for _ in 0..<temp[1] {
              let t = readLine()!.split(separator: " ").map{ Int($0)! }
              let first = t[0]
              let second = t[1]
              
              links[second].append(first)
          }
      }
      
      private func calc() {
          for num in 1...N {
              visited = .init(repeating: false, count: N + 1)
              let result = bfs(num)
              hackingCount[num] = result
              maxCount = max(result, maxCount)
          }
      }
      
      private func dfs(_ num: Int) -> Int {
          visited[num] = true
          if links[num].isEmpty { return 1 }
          
          var count = 1
          
          for val in links[num] {
              if visited[val] { continue }
              count += dfs(val)
          }
          
          return count
      }
      
      private func bfs(_ num: Int) -> Int {
          var queue = [Int]()
          queue.append(num)
          
          var count = 1
          
          while !queue.isEmpty {
              let now = queue.remove(at: 0)
              
              for val in links[now] {
                  if visited[val] { continue }
                  count += 1
                  visited[val] = true
                  queue.append(val)
              }
          }
          
          return count
      }
      
      private func printAnswer() {
          for index in hackingCount.indices {
              if hackingCount[index] == maxCount {
                  print(index, separator: "", terminator: " ")
              }
          }
      }
  }
  
  BJ1325().solve()
  

  • 시간,메모리

  와 BFS도 시간초과 나네!!! 하하핳하ㅏㅎ하하하핳