BOJ - 15591 MooTube(Silver)

leehyunjon·2022년 6월 12일

boj 그래프 이론 인접리스트 인접배열

Algorithm

목록 보기

59/162

15591 MooTube(Silver) : https://www.acmicpc.net/problem/15591

Problem

Solve

BFS를 돌면서 Q[i]에서 질문하는 조건에 맞는 채널에 연결되어있는 k이상인 채널의 개수를 반환하는 문제이다.

처음에 풀었을때는 인접배열 방식을 사용해서 질문 반복의 시간 O(5000), BFS시간 O(5000*5000)으로 시간초과가 발생했었다.

인접리스트 방식을 사용하니 질문 반복 시간 O(5000), BFS시간 O(5000+5000)으로 통과가 되었다.

인접 배열방식은 총 V(정점)개를 방문하고 나머지 정점을 모두 방문하는 방식이므로 O(V*V)의 시간 복잡도가 발생한다.

인접 리스트방식은 총 V(정점)개를 방문하고 인접하고 있는 E(간선)개 만큼의 정점만 방문하는 방식이므로 O(V+E)의 시간복잡도가 발생한다.

Code

public class MooTube {
	static int N;
	static int Q;
    //인접 배열방식
	// static int[][] network;
    //인접 리스트방식
	static List<int[]>[] network;
	static int[][] question;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		Q = Integer.parseInt(st.nextToken());

		network = new List[N+1];
		for(int i=0;i<N+1;i++){
			network[i] = new ArrayList<>();
		}
		// network = new int[N+1][N+1];
		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int p = Integer.parseInt(st.nextToken());
			int q = Integer.parseInt(st.nextToken());
			int r = Integer.parseInt(st.nextToken());

			// network[p][q] = r;
			// network[q][p] = r;
			//0 : 채널 번호, 1 : USADO
			network[p].add(new int[]{q,r});
			network[q].add(new int[]{p,r});
		}

		question = new int[Q][2];
		for (int i = 0; i < Q; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			question[i][0] = Integer.parseInt(st.nextToken());
			question[i][1] = Integer.parseInt(st.nextToken());
		}

		StringBuilder sb = new StringBuilder();
		for (int turn = 0; turn < Q; turn++) {
			int count = recommendation(turn);
			sb.append(count);
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	//해당 질문에 대한 추천 채널 개수
	static int recommendation(int turn) {
		int k = question[turn][0];
		int v = question[turn][1];

		Queue<Integer> queue = new LinkedList<>();
		boolean[] visit = new boolean[N+1];
		visit[v] = true;
		queue.add(v);
		int count = 0;

		while(!queue.isEmpty()){
			int current = queue.poll();

			for(int[] channel : network[current]){
				int num = channel[0];
				int usado = channel[1];
				if(!visit[num] && usado >= k){
					visit[num] = true;
					queue.add(num);
					count++;
				}
			}
		}

		return count;
	}
}