[JAVA] 백준 17616번 : 등수 찾기(한국정보올림피아드/KOI 2019 2차대회/초등부)

www.acmicpc.net/problem/17616

17616번: 등수 찾기

문제

그래프를 만들어야 되는 문제라고 생각은 했으나 어떻게 문제를 접근해야할지 몰라서 다른사람 풀이 참고함

참고 블로그: home-body.tistory.com/646

 

해결 방안

가능한 가장 높은 등수 U와 가능한 가장 낮은 등수 V를 구하는 문제이다.

크게 보자면 단방향 그래프로 lower_graph와 higher_graph 두개를 이용해서 U와 V를 구해주었다.

lower_graph는 x에서 시작하는 x보다 뒤의 순서들이 나열될 것이다. 따라서 인접 노드의 갯수를 구한뒤 +1을 해주면 가능한 가장 높은 등수 U가 된다.

higher_graph는 x에서 시작하는 x보다 앞의 순서들이 나열될 것이다. 따라서 n에서 인접노드의 갯수를 빼면 가능한 가장 낮은 등수 V가 될것이다. 

코드

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

//한국정보올림피아드
//KOI 2019 2차대회 초등부
//등수 찾기
public class Main {

	static int n, m, x;
	static int u, v; // u가 가능한 가장 높은 등수, v가 가능한 가장 낮은 등수
	
	static ArrayList<ArrayList<Integer>> higer_graph;
	static ArrayList<ArrayList<Integer>> lower_graph;
	static boolean[] visited;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str = br.readLine();
		n = Integer.parseInt(str.split(" ")[0]);
		m = Integer.parseInt(str.split(" ")[1]);
		x = Integer.parseInt(str.split(" ")[2]);
		
		higer_graph = new ArrayList<>();
		lower_graph = new ArrayList<>();
		
		
		for(int i=0; i<n+1; i++) {
			higer_graph.add(new ArrayList<Integer>());
			lower_graph.add(new ArrayList<Integer>());
		}
		
		// 단방향 그래프
		int a,b;
		for(int i=0; i<m; i++) {
			str = br.readLine();
			a = Integer.parseInt(str.split(" ")[0]);
			b = Integer.parseInt(str.split(" ")[1]);
			
			higer_graph.get(a).add(b);
			lower_graph.get(b).add(a);
		}
		
		System.out.println((1+bfs(x, lower_graph)) + " " + (n-bfs(x, higer_graph)));
		
	}
	
	public static int bfs(int start, ArrayList<ArrayList<Integer>> graph) {
		visited = new boolean[n+1];
		
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		visited[start] = true;
		int result = 0;
		
		int current;
		int y; // 인접노드
		while(!q.isEmpty()) {
			current = q.poll();
			//System.out.print(current + " ");
			
			for(int i=0; i<graph.get(current).size(); i++) {
				y = graph.get(current).get(i);
				
				if(!visited[y]) {
					q.offer(y);
					visited[y] = true;
					result++;
				}
			}
		}
		//System.out.println();
		return result;
	}

}