[백준 17616] 등수 찾기 (Java)

문제 링크: https://www.acmicpc.net/problem/17616

17616번: 등수 찾기

1. 주의할 점

- N≤10^5이므로 간선들의 정보를 나타내는 2차원 배열을 사용하지 않는다

 

2. 구현

- 가장 높은 등수는 1+ (해당 학생보다 잘 본 학생 수)

- 가장 낮은 등수는 전체 학생수 - (해당 학생보다 못 본 학생 수)

- Check[][2] 배열을 통해 각 Node를 방문했는지 검사한다([][0]: 정방향, [][1]: 역방향)

- Li[][2] 리스트를 통해 정방향과 역방향에 대한 간선들이 정보를 담는다

- Spread() 함수를 통해 해당 학생으로부터 앞과 뒤에 몇명이 있는지 각각 구한다

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    static boolean check[][];
    static List<Integer> li[][];
    static int num,query,student;
    
    static int spread(int flag){
        Queue<Integer> q = new LinkedList<>();
        check[student][flag]=true;
        q.offer(student);
        int cnt=0;
        
        while(!q.isEmpty()){
            int cur = q.poll();
            for(int i=0;i<li[cur][flag].size();i++){
                int next = li[cur][flag].get(i);
                if(!check[next][flag]){
                    check[next][flag]=true;
                    q.offer(next);
                    cnt++;
                }
            }
        }
        return cnt;
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    num = Integer.parseInt(st.nextToken());
	    query = Integer.parseInt(st.nextToken());
	    student = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    check = new boolean[num+1][2];
	    li = new List[num+1][2];
	    for(int i=1;i<=num;i++){
	        li[i][0] = new ArrayList<>();
	        li[i][1] = new ArrayList<>();
	    }	    
	    for(int i=0;i<query;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        int pre = Integer.parseInt(st.nextToken());
	        int post = Integer.parseInt(st.nextToken());
	        li[pre][0].add(post);
	        li[post][1].add(pre);
	    }
	    int best = 1+spread(1);
	    int worst = num-(spread(0));
	    System.out.println(best+" "+worst);
	}
}