백준 - 15591 MoonTube Gold5 풀이

풀러가기

해당 문제를 보았을 때 보이는 건 주어진 그래프가 트리라는 것이다.

그 다음에 존은 이 동영상들을 네트워크 구조로 바꿔서, 각 동영상을 정점으로 나타내기로 했다. 또 존은 동영상들의 연결 구조를 서로 연결되어 있는 N-1개의 동영상 쌍으로 나타내었다. 좀 더 쉽게 말해서, 존은 N-1개의 동영상 쌍을 골라서 어떤 동영상에서 다른 동영상으로 가는 경로가 반드시 하나 존재하도록 했다.

그래프 중 다음 속성을 만족하면 트리라고 할 수 있다.

• 모든 노드간 연결되어 있고
• N개의 정점일 때 N-1개의 간선을 가지고 있다는 것이다.
• 루트에서 다른 임의의 노드로 가는 경로는 유일하다. 즉 두 정점 사이 경로가 유일하게 존재한다.

문제는 간단하다. 각 노드간 DFS, BFS를 통해 각 정점에서 다른 정점까지의 유사도를 구하면 된다.

import sys
import math
import time
sys.setrecursionlimit(10000)

N,Q = map(int, sys.stdin.readline().split())
adjlist = [[] for _ in range(N+1)]
usado = [[ -1 for _ in range(N+1)] for _ in range(N+1)]
visit = [False for _ in range(N+1)]
def dfsUsado(start,cur,curUsado):

    if not visit[cur]:
        visit[cur] = True           
        retUsado = curUsado
        for nextNode in adjlist[cur]:
            if not visit[nextNode]:
                usado[start][nextNode] = min(curUsado, usado[cur][nextNode])
                usado[nextNode][start] = min(curUsado, usado[cur][nextNode])
                dfsUsado(start,nextNode,usado[start][nextNode])
    return 

from collections import deque
def bfsUsado(start):
    dq = deque()
    visit = [False for _ in range(N+1)]
    dq.append((start,sys.maxsize))

    while dq:
        cur, curUsado = dq.popleft()
        
        if visit[cur]:
            continue

        visit[cur] = True

        for nextNode in adjlist[cur]:
            if not visit[nextNode]:
                temp = min(curUsado, usado[cur][nextNode])
                usado[start][nextNode] = temp
                usado[nextNode][start] = temp
                dq.append((nextNode, temp))
            

for _ in range(N-1):
    p,q,r = map(int, sys.stdin.readline().split())
    adjlist[p].append(q)
    adjlist[q].append(p)
    usado[p][q] = r
    usado[q][p] = r

for i in range(1,N+1):
    bfsUsado(i)
	// 위에는 bfs 밑에는 dfs 방식
    visit = [False for _ in range(N+1)]
    dfsUsado(i,i,sys.maxsize)
    
for _ in range(Q):
    k,v = map(int, sys.stdin.readline().split())
    count = 0 
    for u in usado[v]:
        if u != -1 and u >= k:
            count += 1
    print(count)

파이썬을 문제를 풀 때 bfs로는 통과를 하나 dfs 코드는 시간초과가 발생한다.
자바로 문제를 풀 때는 둘 다 통과!

오랜만에 프로그래머스 말고 백준 문제를 풀어서인가 어색하긴했다..