[백준] 2458번:키 순서 (Java 자바)

문제

https://www.acmicpc.net/problem/2458

2458번: 키 순서

 

 

풀이 및 소스코드

 

bfs로 풀었다.

리스트에 담을 때 본인보다 큰 사람만 담는 리스트 하나, 작은 사람만 담는 리스트 하나 이렇게 두개를 만들어서

각각 bfs 돌려주었다. 

 

이 문제에서 느낀 ArrayList와 LinkedList 구분의 중요성..!

처음에는 그냥 LinkedList로 풀었으나, 생각해보니 삽입삭제보다는 조회가 더 많은 경우라 ArrayList로 다시 바꿔 풀었는데 아래와 같이 엄청난 차이가 났다.

위 : ArrayList, 아래 : LinkedList

삽입삭제가 빈번할 때 : LinkedList 사용

조회가 빈번할 때 : ArrayList 사용 하는 것을 잊지 말자.. !

 

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 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		ArrayList<Integer>[] bg = new ArrayList[n];
		ArrayList<Integer>[] sg = new ArrayList[n];
		for(int i=0;i<n;i++) {
			sg[i] = new ArrayList<Integer>();
			bg[i] = new ArrayList<Integer>();
		}
		
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken())-1;
			int b = Integer.parseInt(st.nextToken())-1;
			bg[a].add(b);
			sg[b].add(a);
		}
		
		int res = 0;
		for(int i=0;i<n;i++) {
			// 0번쨰 학생부터 키순서 알아보기
			
			// 큰 사람 알아보기
			boolean[] c = new boolean[n];
			c[i] = true;
			int cnt = 0;
			Queue<Integer> q = new LinkedList<>();
			q.add(i);
			while(!q.isEmpty()) {
				int x = q.poll();
				for(int nowx:bg[x]) {
					if(!c[nowx]) {
						q.add(nowx);
						cnt++;
						c[nowx] = true;
					}
				}
			}
			
			
			// 작은사람 알아보기
			q = new LinkedList<>();
			q.add(i);
			while(!q.isEmpty()) {
				int x = q.poll();
				for(int nowx:sg[x]) {
					if(!c[nowx]) {
						q.add(nowx);
						cnt++;
						c[nowx] = true;
					}
				}
			}
			
			if(cnt==n-1) {
				res++;
			}
		}
		System.out.println(res);
	}
}