[릿코드 2492] Minimum Score of a Path Between Two Cities (파이썬/python)

https://leetcode.com/problems/minimum-score-of-a-path-between-two-cities/description/

Minimum Score of a Path Between Two Cities - LeetCode

보자마자 아! 유니온파인드 쓸까? 라고 생각했지만 

일단 익숙한 dfs 로 문제를 풀어보았고 시간초과가 났다.

 

dfs 의 빅오자체는 크지 않았지만 생각보다 문제 조건상 많은 연산을 처리해야되기때문에 안됐다

옛날에 프로그래머스에서 표병합 이라는 문제를 풀며 유니온파인드를 써본경험이있어서 어렵지 않게 코드를 작성할 수 있었다.

 

 

https://ip99202.github.io/posts/%EC%9C%A0%EB%8B%88%EC%98%A8-%ED%8C%8C%EC%9D%B8%EB%93%9C(Union-Find)/ 

유니온 파인드(Union-Find)

유니온파인드개념은 이곳 참고

 

 

틀린풀이 : dfs

from typing import List


class Solution:
    def __init__(self):
        self.min_distance = 10 ** 4 + 1
        self.visit = []

    def minScore(self, n: int, roads: List[List[int]]) -> int:
        graph = [[] for _ in range(n + 1)]
        self.visit = [[False for _ in range(n + 1)] for _ in range(n + 1)]

        # 그래프 연결
        for road in roads:
            a_node, b_node, distance = road

            graph[a_node].append((b_node, distance))
            graph[b_node].append((a_node, distance))

        self.dfs(1, graph)
        print(self.min_distance)
        return self.min_distance

    def dfs(self, current: int, graph: List[List[tuple]]):

        for target in graph[current]:
            target_node, target_distance = target
            if not self.visit[current][target_node]:
                self.visit[current][target_node] = True
                self.visit[target_node][current] = True
                self.min_distance = min(self.min_distance, target_distance)
                self.dfs(target_node, graph)

 

 

 

맞은 풀이:유니온파인드

from typing import List


class Solution:
    def __init__(self):
        # 문제 조건상 나올 수 없는 정답값
        self.min_score = 10 ** 4 + 1
        self.parent = {}
        self.score_dic = {}

    def minScore(self, n: int, roads: List[List[int]]) -> int:
        maximum_score = 10 ** 4 + 1

        for road in roads:
            a_node, b_node, score = road
            self.score_dic[a_node] = min(self.score_dic.get(a_node, maximum_score), score)
            self.score_dic[b_node] = min(self.score_dic.get(b_node, maximum_score), score)

            self.merge(a_node, b_node, n)

        self.find_min_score(n)
        return self.min_score

    def find(self, node: int) -> int:
        if node not in self.parent:
            self.parent[node] = node
        else:
            if self.parent[node] == node:
                return node

            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def merge(self, node_a: int, node_b: int, n: int):
        # 서로의 최상위 노드를 찾음
        node_a = self.find(node_a)
        node_b = self.find(node_b)

        # 이미 최상위 부모가 같다면 이미 연결된 노드
        if node_a == node_b:
            return

        # 부모와 부모를 연결, 이때 최상단 부모는 n 이 될 수 있다면 무조건 n 이 되도록 설정한다.
        if node_a == n:
            self.parent[node_b] = n
        elif node_b == n:
            self.parent[node_a] = n
        else:
            self.parent[node_a] = node_b

    def find_min_score(self, n: int):
        for i in range(1, n + 1):
            # 최상단 부모가 n 인 값중에 거리가 가장 작은 것을 찾는다.
            if n == self.find(i):
                self.min_score = min(self.score_dic[i], self.min_score)

 

 

다른 푼의 간결한 풀이:DFS

from collections import defaultdict
from typing import List


class Solution:

    def minScore(self, n: int, roads: List[List[int]]) -> int:
        m = defaultdict(list)
        res = [10 ** 4 + 1]
        visit = set()

        for a, b, dist in roads:
            m[a].append([b, dist])
            m[b].append([a, dist])

        def dfs(node):
            visit.add(node)

            for next_node, dist in m[node]:
                res[0] = min(res[0], dist)

                if next_node in visit:
                    continue
                dfs(next_node)

        dfs(1)
        return res[0]