[Python] BOJ(백준) 15591번 - MooTube (Silver)

링크

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

난이도(solved.ac 참고)

골드5

풀이

BFS 문제이다. 그래프 탐색 문제를 너무 오랜만에 풀어서 갈피를 못잡았다. 인접 그래프 먼저 만들어주고, 노드 방문 여부를 확인하기 위해 visited 배열을 선언해줬으며, 큐에 처음으로 들어갈 값에는 유사도가 존재하지 않으므로 갱신해주기 위해 float('inf')를 넣었다.

 

pop한 값을 기준으로 그래프의 인접 값을 탐색하면서 유사도를 더 낮은 값으로 갱신해주며, 그 갱신한 유사도가 K보다 클 경우에는 큐에 (새로운 노드, 새로운 유사도)를 넣어주고, 방문 처리한다음 갯수에 해당하는 result의 값을 1 더해준다.