[Python] 프로그래머스 Lv 3 - 가장 먼 노드

개고생했던 문제 중 하나. 

출처

알고리즘

그저, 1번노드부터 시작해서 최단거리를 구하면 되는 문제다.
BFS로 depth를 돌려줘도 되고, 다익스트라를 쓰되, 모든 거리를 1이라고 가정해도 되는 문제다.

주의할 점은, edge의 집합이 주어져 있는데, 모든 vertex에 대해 edge의 유무를 따질 경우 시간초과가 난다.

따라서, dict를 만들어야 하는데, 각 꼭지점으로 연결된 상태 파악을 위해서는 defaultdict를 활용하여, 각 꼭지점마다 연결된 다른 점들의 list를 만들어줘야 한다. 

코드(1트, 실패)

그저 bfs로 푼 코드이다. 시간 초과가 걸려 실패했으며,
빼는 방향과 넣는 방향이 반대로 해야 성공하는데, 아직까지도 정확한 이유를 판단하지 못했다.
따라서, 더 확실한 방향인 다익스트라로의 전환을 고려했다.

from collections import deque, Counter
def bfs(visited, distance, vertex):
    queue = deque()
    queue.append(1)
    curr_dist = 0
    
    while queue:
        curr = queue.pop()
        visited[curr] = 1
        for node in vertex:
            if curr in node:
                if node[0] == curr:
                    next = node[1]
                else: 
                    next = node[0]                    
                if visited[next] == 0:
                    if distance[next] == 0:
                        distance[next] = distance[curr] + 1
                    else:
                        distance[next] = min([distance[next], distance[curr]+1])
                    queue.appendleft(next)    
    return distance
def solution(n, edge):
    distance = [0 for _ in range(n+1)] # 1번부터 n+1번까지
    visited = [0 for _ in range(n+1)]
    answer_list = bfs(visited, distance, edge)
    
    max_dist = (dict(Counter(answer_list)))
    max_dist = sorted(max_dist.items(), reverse=True)
    return max_dist[0][1]

코드(2트, 실패)

다익스트라로 변경한 코드. 역시 효율성이 나빠서인지 실패.

# 전부 거리가 1인 다익스트라로 풀어버리자.
from collections import Counter
from queue import PriorityQueue
def dijkstra(n, vertex):
    queue = PriorityQueue()
    queue.put([1, 0])
    dist = [float('inf')] * (n+1)
    dist[0] = -1
    dist[1] = 0
    
    while not queue.empty():
        curr, curr_dist = queue.get()
        for node in vertex:
            if curr in node:
                if node[0] == curr:
                    next = node[1]
                else:
                    next = node[0]
                if dist[next] > curr_dist + 1:
                    dist[next] = curr_dist + 1
                    queue.put([next, curr_dist + 1])
    return dist            
    
def solution(n, edge):
    answer_list = dijkstra(n, edge)
    max_dist = (dict(Counter(answer_list)))
    max_dist = sorted(max_dist.items(), reverse=True)
    return max_dist[0][1]

코드(3트, 실패)

3트에서는 위의 코드 기반으로, edge를 탐색하는 방식을 바꿔 시도해보았다. 

# 전부 거리가 1인 다익스트라로 풀어버리자.
from collections import Counter
from queue import PriorityQueue
def dijkstra(n, adj_matrix):
    queue = PriorityQueue()
    queue.put([1, 0])
    dist = [float('inf')] * (n+1)
    dist[0] = -1
    dist[1] = 0
    
    while not queue.empty():
        curr, curr_dist = queue.get()
        for next in range(0, n+1):
            if adj_matrix[curr][next] == 1:
                if dist[next] > curr_dist + 1:
                    dist[next] = curr_dist + 1
                    queue.put([next, curr_dist + 1])
    return dist            
    
def solution(n, edge):
    adj_matrix = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i, j in edge:
        adj_matrix[i][j] = 1
        adj_matrix[j][i] = 1
    
    answer_list = dijkstra(n, adj_matrix)
    print(answer_list)
    max_dist = (dict(Counter(answer_list)))
    max_dist = sorted(max_dist.items(), reverse=True)
    return max_dist[0][1]

코드(4트, 성공)

결국 질문끝에, dict로 바꿔 풀어야함을 깨달았고, 그 방법을 잘 몰랐는데 defaultdict를 통해 해결 가능했다.

# 전부 거리가 1인 다익스트라로 풀어버리자.
from collections import Counter, defaultdict
from queue import PriorityQueue
def dijkstra(n, graph):
    queue = PriorityQueue()
    queue.put([1, 0])
    dist = [float('inf')] * (n+1)
    dist[0] = -1
    dist[1] = 0
    
    while not queue.empty():
        curr, curr_dist = queue.get()
        for next in graph[curr]:
                if dist[next] > curr_dist + 1:
                    dist[next] = curr_dist + 1
                    queue.put([next, curr_dist + 1])
    return dist            
    
def solution(n, edge):
    # Point. graph와 노드를 별도로 이렇게 리스트로 저장해야한다.
    graph = defaultdict(list)
    for i, j in edge:
        graph[i].append(j)
        graph[j].append(i)
        
    answer_list = dijkstra(n, graph)
    return answer_list.count(max(answer_list))

 

회고

1. 다익스트라 알고리즘을 이전에 배웠던 문제를 바탕으로 조금 변형해서 썼는데, 이 참에 제대로 다시 배워야겠다.

2. dict를 활용하여 탐색 수를 줄이는 것에 익숙해져야겠다.