[백준] 15591 - MooTube / Python / 골드 5

🚩문제 주소

📄풀이

그래프 탐색

문제를 보고 해석했는데 그래프 탐색 문제인 것을 깨달았습니다. 그런데 정확히 요구하는게 뭔지 너무 헷갈렸습니다. 그래서 검색을 통해 문제 해석을 찾아봤는데 그냥 조건이 딱히 까다롭지 않은 그래프 탐색 문제였습니다.

1. defaultdict를 활용해서 p, q, r을 입력 받을 때 인접 그래프를 만들어줍니다.
2. k, v를 입력 받아서 bfs함수에 인자로 넣은 후 결과를 출력합니다.

bfs 함수

def bfs(K, num):
  visited = [0]*(len(video.keys())+1)
  cnt = 0
  q = deque()
  q.append(num)
  visited[num] = 1

  while q:
    n = q.popleft()
    for v in video[n]:
      if not visited[v[0]] and v[1] >= K:
        visited[v[0]] = 1
        cnt += 1
        q.append(v[0])

  return cnt

먼저 deque와 방문 확인할 배열, 반환할 카운트 변수를 선언해줍니다.
deque에 입력받은 동영상 번호를 넣고 방문 체크를 해줍니다.

deque에서 popleft한 번호를 그래프에서 탐색합니다.
방문한 적이 없고 k가 K보다 같거나 크다면 방문 체크, 카운트 +1, deque에 동영상 번호를 추가합니다.

탐색이 종료되면 카운트를 반환합니다.

👨‍💻코드

from collections import defaultdict, deque

def bfs(K, num):
  visited = [0]*(len(video.keys())+1)
  cnt = 0
  q = deque()
  q.append(num)
  visited[num] = 1

  while q:
    n = q.popleft()
    for v in video[n]:
      if not visited[v[0]] and v[1] >= K:
        visited[v[0]] = 1
        cnt += 1
        q.append(v[0])

  return cnt

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

for _ in range(Q):
  k, v = map(int, input().split())
  print(bfs(k, v))