[알고리즘] 백준 - 특정 거리의 도시 찾기 18352번(JAVA)

이번 문제에서 약간의 난항(?)을 겪었다. ArrayList와 LinkedList를 섞어서 쓰던 탓이었는지 이번 문제에서는 LinkedList를 선택해서 문제를 풀었다. 이 때문에 시간초과 라는 문제에 계속 놓였다.

알고보니 LinkedList와 ArrayList에는 속도 차이가 난다는 점을 알 수 있었다. add 나 get 메서드를 사용할 때는 큰 차이가 없으나 큰 메모리를 사용하는 경우 차이가 날 수 있다.

ArrayList는 공간이 부족한 경우 새로 배열을 resize하는 과정을 거치며, LinkedList는 그럴 필요없이 주소만 가진채 연결만 해주면 된다. 따라서 시간 복잡도는 동일하지만, ArrayList의 resize하는 시간때문에 LinkedList보다는 느리다.

하지만 ArrayList에 initial capacity를 넉넉히 할당해준다면 LinkedList보다 더 빠르게 접근할 수 있다. 이유는, 초기 capacity인 10보다 resize하는 동작이 줄기 때문이다.

만약 initial capacity를 1000으로 넉넉히 해준 경우 실험을 해본 결과는 평균 119101ms가 결렸다고 한다. LinkedList와 같은 시간 복잡도를 가지지만, 더 빠른 속도임을 알 수 있다.

또한 위 표와 같이 get이나 set을 사용하는 경우가 많다면 ArrayList를 사용하면 되고, 반대로 시작/끝에 add나 remove를 사용하는 경우가 많다면 LinkedList를 사용하면 된다.

결론1

ArrayList가 더 빠르게 접근할 수 있고 빠른 속도를 보여줄 수 있다.
얼마의 데이터가 입력이 될지 모르는 상황에서는 LinkedList를 사용하고, 큰 데이터를 사용하는 경우 ArrayList를 resize하여 사용하도록 한다.

결론 2

일반적으로 get/set을 자주 사용하는 경우 = ArrayList
처음이나 끝에 add/remove를 자주 사용하는 경우 = LinkedList

백준 - 특정 거리의 도시 찾기

import java.util.*;
import java.io.*;
class Solution{
	static class Pair{
		int node;
		int dist;
		Pair(int node, int dist){
			this.node = node;
			this.dist = dist;
		}
	}
	static ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
	static int n, m, k, x;
	static boolean v[];
	static int dist[];
	public static void main(String args[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		k = Integer.parseInt(st.nextToken());
		x = Integer.parseInt(st.nextToken());
		v = new boolean[n+1];
		dist = new int[n+1];
		
		for(int i=0;i<n+1;i++) {
			list.add(new ArrayList<>());
			dist[i] = -1;
		}
		
		while(m-- >0) {
			st = new StringTokenizer(br.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			list.get(a).add(b);
		}
		
		find();
		
		boolean check = false;
		for(int i=1;i<n+1;i++) {
			if(dist[i] == k) {
				sb.append(i).append("\n");
				check = true;
			}
		}
		
		if(!check) sb.append(-1);
		
		System.out.println(sb);
		
	}
	public static void find() {
		Queue<Pair> q = new LinkedList<>();
		q.add(new Pair(x, 0));
		dist[x] = 0;
		
		while(!q.isEmpty()) {
			Pair now = q.poll();
			
			List<Integer> sub = list.get(now.node);
			for(int i=0;i<sub.size();i++) {
				int a = sub.get(i);
				if(dist[a] == -1) {
					dist[a] = now.dist+1;
					if(dist[a] != k)
						q.add(new Pair(a, now.dist+1));
				}
			}
		}
	}
	
}

위에서 list선언을 LinkedList로 선언했던 것을 ArrayList로 바꿔주니 시간초과나던게 갑자기 성공이 뜬다......