[BJ] 백준 15591 MooTube (Silver) (JAVA)

문제

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

 

풀이 방법

이 문제는 시간초과가 관건인 문제였다. 
처음에는 인접 행렬로 풀이를 하려고 했는데 계속해서 시간초과가 발생했다.
그래서 도저히 시간을 단축시킬 방법이 생각이 안나서 찾아봤더니 인접 리스트를 사용하면 풀리는 문제였다.
풀이 과정은 다음과 같다.

1. 인접 리스트를 생성해서 인접한 정점들과 USADO 값을 저장해준다.
2. v번째 정점으로부터 BFS를 시작한다.
3. queue에서 poll를 한 정점(n)과 인접하고(USADO값이 존재) 방문하지 않은 정점들만 탐색 후보가 된다.
4. n번 정점과 탐색 후보 사이의 USADO 값이 k이상인 경우에만 que에 넣어준다.
5. 그리고 cnt도 하나 증가해준다. 왜냐면 visit배열의 값을 true로 변경해주면서 현재 후보 정점은 다시는 나올 가능성이 없다. 즉, 도착지라고 생각해주면 된다. (후보로 나왔다는 거 자체가 v번 정점에서 출발해서 도착할 수 있다는 의미. 그러므로 추천 영상의 개수 cnt에 1를 더해준다.)
6. cnt를 출력해준다.

 

사실 인접 행렬과 인접 리스트를 언제 사용해야하는지도 잘 감이 안왔고,  매번 인접 행렬만 사용했기 때문에 이 문제를 풀 때 인접 리스트를 생각하지 못했다.

그런데 갑자기 문제를 풀다가 왜 두 개가 시간 차이가 발생을 하는지 의문이 생겼다. 인접 행렬에 인접하지 않는다는 걸 조건으로 걸어주면 비슷할 것이라고 단순하게 생각했던 것 같다. 

그래서 BFS의 시간 복잡도를 찾아봤다. 

 

BFS의 시간 복잡도

1. 인접 행렬

- 인접 행렬에서 BFS를 사용하면 우선 모든 정점을 다 방문을 하기 때문에 O(V)의 시간이 걸린다. 그리고 하나의 정점마다 또 V개의 정점을 방문하므로 O(V*V) = O(V^2) 의 시간 복잡도를 갖는다.

 

2. 인접 리스트

- 인접 리스트에서도 우선 모든 정점을 방문하므로 O(V)의 시간이 걸린다. 그리고 각 방문한 정점에서 인접한 간선들만 방문을 하기 때문에 총 간선의 개수인 O(E)의 시간을 추가로 갖는다. 그래서 인접리스트의 시간 복잡도는 O(V+E)이다.

 

처음에 찾아봤을 때 인접 행렬은 이해가 잘 됐는데 인접리스트는 왜 저렇게 나오는지 이해가 잘 안됐다.

어짜피 주어진 간선들만 방문하니 O(E)라고 생각했다. 그런데 좀 더 찾아보면서 간선을 방문하기 전 정점들도 방문을 하기 때문에 O(V) 만큼의 시간이 발생하고, 그래서 O(V+E)라는 것을 이해할 수 있었다. 

보통 간선이 많다면 인접 행렬을, 간선이 적다면 인접 리스트를 사용한다고 한다.

 

이렇게 찾아보고 나니 사실 인접 행렬이 시간이 더 오래 걸리는게 당연하다는 생각이 들었다.

두 개의 방법은 각각 장단점이 존재하기 때문에 상황에 따라서 선택해서 사용한다. 이 문제에서는 비교적 간선이 적은 편이였고, 그래서 인접 리스트를 사용하면 더 효율적인 문제였던 것 같다. 앞으로 시간 복잡도를 생각해서 문제를 풀어보도록 해야겠다......

 

제출 코드

<인접 리스트>

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

public class BOJ_15591_MooTube {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());

		ArrayList<int[]>[] list = new ArrayList[N]; //인접 리스트
		for (int i = 0; i < N; i++) {
			list[i] = new ArrayList<int[]>();
		}
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken()) - 1;
			int q = Integer.parseInt(st.nextToken()) - 1;
			int usado = Integer.parseInt(st.nextToken());
			list[p].add(new int[] { q, usado });
			list[q].add(new int[] { p, usado });
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken()) - 1;
			Queue<Integer> que = new LinkedList<Integer>();
			boolean[] visit = new boolean[N];
			que.add(v); visit[v] = true;
			int cnt = 0;
			while(!que.isEmpty()) { //BFS
				int n = que.poll();
				for (int j = 0; j < list[n].size(); j++) { //인접한 정점들만 탐색
					int[] t = list[n].get(j);
					if(!visit[t[0]] && t[1] >= k) { //방문하지 않았고, USADO가 k이상인 것만 탐색
						que.add(t[0]);
						visit[t[0]] = true;
						cnt++;
					}
				}
			}
			sb.append(cnt).append('\n');
		}
		System.out.println(sb);
	}
}

 

<인접 행렬>

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

public class BOJ_15591_MooTube2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());
		int[][] USADO = new int[N][N];

		for (int i = 0; i < N; i++) {
			Arrays.fill(USADO[i], -1);
		}

		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken()) - 1;
			int q = Integer.parseInt(st.nextToken()) - 1;
			int usado = Integer.parseInt(st.nextToken());
			USADO[p][q] = USADO[q][p] = usado;
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken()) - 1; //출발
			int cnt=0;
			boolean[] visit = new boolean[N];
			Queue<Integer> que = new LinkedList<Integer>();
			que.add(v);
			visit[v] = true;
			while(!que.isEmpty()) {
				int n = que.poll();
				for (int j = 0; j < N; j++) {
					if(!visit[j] && USADO[n][j] >= k) {
						que.add(j);
						visit[j] = true;
						cnt++;
					}
				}
			}
			sb.append(cnt).append('\n');
		}
		System.out.println(sb);
	}
}

 

 

참고

https://currygamedev.tistory.com/10