[백준] 15591 MooTube (파이썬 Python)

2024. 2. 5. 14:46· Algorithm
목차
  1. 문제 링크
  2. 문제 풀이

 

문제 링크

 

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

 

15591번: MooTube (Silver)

농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의

www.acmicpc.net

 

 

문제 풀이

 

한 노드와 다른 노드 사이의 usado가 그 사이의 usado의 최솟값이라는 조건을 보고

처음에는 해당 조건을 활용해서 usado들을 모두 저장해놓고 결과를 구해야하나 했습니다.

그것보다는 bfs를 활용하여 노드를 하나씩 이동하며 usado를 최솟값으로 갱신하고

k보다 usado가 클 경우 결괏값을 1씩 증가시키는 것이 효율적일 것 같았습니다.

 

def bfs(k, v):
    visited = [0] * (n + 1)
    visited[v] = 1
    result = 0
    queue = deque([(v, 1e9)])
    while queue:
        v, usado = queue.pop()
        for n_v, n_usado in graph[v]:
            n_usado = min(usado, n_usado)
            if n_usado >= k and not visited[n_v]:
                result += 1
                queue.append((n_v, n_usado))
                visited[n_v] = 1
    return result

 

visited 체크를 해나가면서 중복 없이 모든 동영상에 대한 Usado를 확인할 수 있게합니다.

문제에서 주어진 하나의 노드에 대해 연결된 모든 노드를 확인하며 가중치를 최소값으로 갱신하고

해당 가중치가 k보다 크며, 노드를 방문하지 않았을 경우 추천되는 목록에 추가됩니다.

해당 노드에 대해 같은 작업을 반복하기 위해 queue에 넣어줍니다.

 

 

전체 코드

from collections import deque, defaultdict

def bfs(k, v):
    visited = [0] * (n + 1)
    visited[v] = 1
    result = 0
    queue = deque([(v, 1e9)])
    while queue:
        v, usado = queue.pop()
        for n_v, n_usado in graph[v]:
            n_usado = min(usado, n_usado)
            if n_usado >= k and not visited[n_v]:
                result += 1
                queue.append((n_v, n_usado))
                visited[n_v] = 1
    return result


n, q = map(int, input().split())
graph = defaultdict(list)
for _ in range(n - 1):
    a, b, w = map(int, input().split())
    graph[a].append((b, w))
    graph[b].append((a, w))
for _ in range(q):
    k, v = map(int, input().split())
    print(bfs(k, v))
저작자표시 비영리 변경금지 (새창열림)

'Algorithm' 카테고리의 다른 글

[Kotlin] 리스트 정렬  (0) 2024.02.01
[백준] 2217 로프 (코틀린 kotlin)  (0) 2024.02.01
[백준] 11047 동전 0 (코틀린 kotlin)  (0) 2024.02.01
코틀린으로 코딩테스트 준비하기  (0) 2024.02.01
[Softeer] 금고털이 Lv.2 (파이썬 python)  (0) 2024.01.31
  1. 문제 링크
  2. 문제 풀이
'Algorithm' 카테고리의 다른 글
  • [Kotlin] 리스트 정렬
  • [백준] 2217 로프 (코틀린 kotlin)
  • [백준] 11047 동전 0 (코틀린 kotlin)
  • 코틀린으로 코딩테스트 준비하기
YOONJELLY
YOONJELLY
YOONJELLY
JELLYJELLY
YOONJELLY
전체
오늘
어제
  • 분류 전체보기 (153)
    • Springboot (2)
    • Android (15)
    • Algorithm (126)
      • 개념 (8)
      • BOJ (91)
      • Programmers (15)
      • SWEA (4)
    • 경험_기록 (1)
    • RIM_TIP (4)
    • Github (2)
    • CS (1)
      • 운영체제 (1)
      • 컴퓨터네트워크 (0)
      • 정보처리기사 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • Python
  • 자료구조
  • SWEA
  • softeer
  • BFS
  • 스택
  • 이진탐색
  • 정렬
  • 큐
  • 완전탐색
  • Android
  • 프로그래머스
  • 이것이코딩테스트다
  • kotlin
  • 딕셔너리
  • 백준
  • 액티비티컴포넌트
  • DP
  • 코딩테스트
  • 문자열
  • programmers
  • 안드로이드
  • DFS
  • 파이썬
  • 소프티어
  • 코틀린
  • BOJ
  • 그리디
  • 알고리즘
  • 다이나믹프로그래밍

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
YOONJELLY
[백준] 15591 MooTube (파이썬 Python)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.