Dijkstra (1) 썸네일형 리스트형 [Leetcode] 743번 - 네트워크 딜레이 시간 1. 문제 파악문제 링크: https://leetcode.com/problems/network-delay-time/문제 정의: n개의 정점에서 시작 정점로부터 가장 늦게 신호를 받는 정점간에 시간을 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 브루트 포스로 문제 풀이 도출그래프에서 노드간에 탐색을 하게 되면 n x n - 1 x n -2 ...이므로 n!이다. 따라서 브루트 포스로 풀면 100!시간을 초과하게된다. 2. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?나의 경우에는 쉽게 풀기 위해서 주어진 2차원 배열로 입력받은 인접 행렬을 만들어서 다익스트라 알고리즘을 구현하였다.n개의 정점이 주어지므로 n x n 인접행렬을 생성하였.. 이전 1 다음