[Python] 프로그래머스. 가장 먼 노드 (Level 3)

 

https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스

주어진 노드를 토대로 n * n Matrix를 생성할 경우 시간초과가 걸리는 문제.

BFS 코드의 효율성보다는 주어진 노드 데이터를 적은 연산비용이 들어가도록 하는 게 관건이었던...

 

 

 

시간초과가 뜨던 코드는 아래와 같았다.

from collections import deque, defaultdict

def bfs(start, maps, visited):
    queue = deque()
    queue.append((start, 0))
    numbers = defaultdict(lambda: 0)
    while queue:
        # print(queue)
        y, cnt = queue.popleft()
        visited[y] = 1
        for x in range(1, len(maps)):
            if visited[x] == 0 and maps[y][x] == 1:
                visited[x] = 1
                queue.append((x, cnt+1))
                numbers[cnt+1] += 1
                
    return numbers[cnt]

def solution(n, edge):
    maps = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for y, x in edge:
        maps[y][x], maps[x][y] = 1, 1
    visited = [0 for _ in range(n+1)]
    return bfs(1, maps, visited)