[알고리즘 / 백준] 15591 - MooTube (Silver)

www.acmicpc.net/problem/15591

15591번: MooTube (Silver)

 

문제는 위와 같으며, DFS 를 통해 연관된 동영상들의 유사도를 확인하여 K보다 크거나 같은 경우 방문한 것으로 표시하고 그 수를 출력하는 방식으로 문제를 해결하였습니다.

 

먼저 예시로 주어진 동영상들의 연관 관계를 그래프로 나타내면 다음과 같습니다.

이후 주어지는 Q 질문과 결과를 하나씩 살펴보면 다음과 같습니다.

 

1. 유사도가 1 이상인 동영상이 추천될 때, 2번 비디오를 보고있는 소들에게 추천될 동영상의 수는?

=> 2번 동영상과 연관된 동영상을 차례대로 살펴보면 모두 유사도가 1 이상이기 때문에 1,3,4번 동영상 모두 추천됩니다. (결과 3)

 

2. 유사도가 4이상인 동영상이 추천될 때, 1번 비디오를 보고 있는 소들에게 추천될 동영상의 수는?

=> 1번 동영상과 연관된 2번 동영상의 유사도가 3으로 기준인 4 미만이기 때문에 추천되는 영상이 없습니다. (결과 0)

 

3. 유사도가 3이상인 동영상이 추천될 때, 1번 비디오를 보고 있는 소들에게 추천될 동영상의 수는?

=> 1번 동영상과 연관된 2번 동영상의 유사도가 3이상이기 때문에 2번 동영상이 추천됩니다. 그리고 2번 동영상과 연관된 3번 동영상의 경우는 유사도가 2로 3미만이기 때문에 추천되지 않고, 4번 동영상은 3이상의 유사도를 가지기 때문에 추천이 되어 최종적으로 2, 4번 동영상이 추천됩니다. (결과 2)

 

따라서, 기준 동영상부터 직접 연결되어 있는 동영상들을 탐색하면 유사도가 K 미만인 동영상의 경우 그 하위로 연결되는 동영상은 더 이상 탐색할 필요가 없기 때문에 DFS 를 사용하여 문제를 해결하였습니다.

 

각 비디오들의 연관 관계를 나타낼 때는 python 의 dictionary, Java 의 Map 구조를 활용하였습니다. 기준 동영상의 번호를 Key 로 사용하고 Value 는 연결된 동영상들의 리스트로 구현하였는데, 각 동영상들은 "동영상 번호"와 "유사도"를 가지는 객체로 생성하였습니다. (python 의 경우는 단순 리스트인 [동영상 번호, 유사도] 형태로 비디오를 구현하였습니다.) 방향성을 가진 그래프가 아니기 때문에 각 비디오마다 연관된 동영상을 모두 추가하였습니다.

해당 방식으로 비디오 간의 관계를 구성하면 배열을 사용할 때보다 효율적으로 탐색을 할 수 있습니다. 

 

이제 코드를 살펴보겠습니다.

 

파이썬 코드는 다음과 같습니다.

import sys


# 연관된 비디오들을 확인하면서 추천되는 동영상의 수를 반환
def dfs(k, v):
    visited = [False] * (n + 1)  # 해당 비디오를 이미 추천했는지 여부 확인
    need_visit = [[v, 1000000000]]  # 연관된 비디오를 확인할 리스트 (초기에는 기준이 되는 비디오 번호와 임시 유사도(최대 유사도)를 추가합니다.)

	# 연관된 비디오를 순차적으로 확인하면서
    while need_visit:
        cv, usado = need_visit.pop()
        if not visited[cv] and usado >= k:  # 해당 비디오가 아직 추천되지 않았고, 그 비디오의 유사도가 K 보다 크거나 같은 경우
            visited[cv] = True  # 해당 비디오를 추천하고
            need_visit.extend(videos[cv])  # 그 비디오와 연관된 비디오들을 확인 리스트에 추가합니다.

    count = visited.count(True)  # 추천된 비디오의 수를 세서
    return count - 1  # 기준이 되었던 비디오를 뺀 나머지 추천 비디오 수를 반환합니다.


n, q = map(int, sys.stdin.readline().split())
videos = dict()
# 비디오의 연관 관계를 dictionary 형태로 저장
for _ in range(n-1):
    a, b, r = map(int, sys.stdin.readline().split())
    if a in videos.keys():
        videos[a].append([b, r])
    else:
        videos[a] = [[b, r]]

    if b in videos.keys():
        videos[b].append([a, r])
    else:
        videos[b] = [[a, r]]

answer = []
# 질문을 하나씩 확인하면서, dfs 를 수행하여 추천 비디오 수 저장
for _ in range(q):
    k, v = map(int, sys.stdin.readline().split())
    answer.append(dfs(k, v))

# 결과 출력
print('\n'.join(map(str, answer)))

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int n;
    private static Map<Integer, ArrayList<Video>> videos = new HashMap<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());

        // 비디오들의 연관 관계를 입력받아
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());

            // 연관 관계를 Map 형태로 구성
            makeVideos(a, b, r);
            makeVideos(b, a, r);
        }

        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());

            // 연관된 동영상들을 확인하고, 추천 동영상의 수를 문자열로 저장
            sb.append(dfs(k, v)).append("\n");
        }

        // 결과 출력
        System.out.println(sb);
    }

    // 비디오의 연관 관계를 Map 형태로 구성하는 메소드
    private static void makeVideos(int a, int b, int r) {
        if (videos.containsKey(a)) {
            videos.get(a).add(new Video(b, r));
        } else {
            videos.put(a, new ArrayList<>(Collections.singletonList(new Video(b, r))));
        }
    }

    // 연관된 비디오들을 확인하면서, 추천 비디오의 수를 반환
    private static int dfs(int k, int v) {
        boolean[] visited = new boolean[n + 1];  // 해당 비디오가 추천되었는지 여부
        // 연관된 비디오의 리스트
        // 초기에는 기준 비디오 번호와 임시 유사도 (최대 유사도)를 추가
        Deque<Video> needVisit = new ArrayDeque<>(Collections.singletonList(new Video(v, 1000000000)));

        // 연관된 비디오들을 확인하면서
        while (!needVisit.isEmpty()) {
            Video cur = needVisit.pop();
            // 아직 해당 비디오가 추천되지 않았고, 그 비디오의 유사도가 K 이상인 경우
            if (!visited[cur.num] && cur.usado >= k) {
                visited[cur.num] = true;  // 해당 비디오를 추천하고 
                needVisit.addAll(videos.get(cur.num));  // 그 비디오와 연관된 비디오를 리스트에 추가
            }
        }

        int count = 0;
        // 추천된 비디오의 수를 확인하고
        for (boolean b : visited) {
            if (b) {
                count += 1;
            }
        }

        return count - 1;  // 초기 기준 비디오를 제외한 추천 동영상 수 반환
    }

    // 비디오 객체
    private static class Video {
        int num;  // 해당 비디오의 번호
        int usado;  // 비디오의 유사도

        public Video(int num, int usado) {
            this.num = num;
            this.usado = usado;
        }
    }
}