[백준][BFS] MooTube (Silver)

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

15591번: MooTube (Silver)

 

내가 작성한 코드

import sys
from collections import defaultdict, deque

read = sys.stdin.readline

def get_input():
    N, Q = map(int, read().rstrip().split())
    graph = defaultdict(lambda: defaultdict(lambda: sys.maxsize))

    for _ in range(N-1):
        one, two, u = map(int, read().rstrip().split())
        one -= 1
        two -= 1
        graph[one][two] = min(graph[one][two], u)
        graph[two][one] = min(graph[two][one], u)

    return N, Q, graph

def get_recommend(N, graph, k, v):
    visited = [False] * N
    visited[v] = True
    q = deque([v])
    recommend = 0

    while q:
        crnt = q.popleft()

        for nw_v, u in graph[crnt].items():
            if not visited[nw_v] and k <= u:
                recommend += 1
                q.append(nw_v)
                visited[nw_v] = True

    return recommend


def get_all_recommend(N, Q, graph):
    for _ in range(Q):
        k, v = map(int, read().rstrip().split())
        print(get_recommend(N, graph, k, v-1))

# main
N, Q, graph = get_input()
get_all_recommend(N, Q, graph)

• 그래프 저장
  
  • dictionary [ VERTEX_FROM ] [ VERTEX_TO ] [ USADO ]
  • 이미 저장된 값과 비교하여 최소값으로 저장
• BFS
  • K보다 작은 경우만 탐색을 이어가며 Vertex 개수 count

 

다른 사람이 작성한 코드

from collections import defaultdict, deque

def find_video(start_n, k, map_dict):
    queue = deque()
    queue.append((start_n, float('inf')))
    visit_list = [-1] * N
    visit_list[start_n] = 1
    count = 0

    while queue:
        pop_node, min_dist = queue.popleft()
        for next_n, dist in map_dict[pop_node]:
            if visit_list[next_n] == 1: continue
            if min_dist > dist:
                queue.append((next_n, dist))
                if dist >= k: count += 1
            else:
                queue.append((next_n, min_dist))
                if min_dist >= k: count += 1
            visit_list[next_n] = 1

    return count


N, Q = map(int, input().split())
map_dict = defaultdict(list)

for _ in range(N-1):
    p, q, r = map(int, input().split())
    map_dict[p-1].append((q-1, r))
    map_dict[q-1].append((p-1, r))

for _ in range(Q):
    k, v = map(int, input().split())
    print(find_video(v-1, k, map_dict))

• float('inf')
  • 무한대를 나타낼 때 많은 분들이 사용함
  • 나는 sys.maxsize를 사용하는데, float('inf')가 더 안전할 수 있음 (inf에 연산시 inf)

https://coreenee.github.io/2020/10/28/%EB%B0%B1%EC%A4%8015591(MooTube)/ 

BAEKJOON 15591

기억해야할 것

• defaultdict default value
  
  • defautdict(lamba: 1)