Coding Test/Shortest path (3) 썸네일형 리스트형 [Programmers] 1844 - 게임 맵 최단거리 1. 문제 파악문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/1844문제 정의: 맵에서 값이 0이 아닌 1인곳으로만 상하좌우 이동해서 시작지점으로부터 도착지점까지 최단거리를 구하는 문제이다.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?해당 문제는 가중치가 없으므로 다익스트라와 같은 최단 경로 풀이보단 BFS를 사용하는 것이 더 적합하다고 생각했다.추가적으로 각 간선이 동일 가중치라면, DFS와 BFS 차이는 아래와같다.DFS는 탐색 과정에서 깊이를 끝까지 탐색하기 때문에, 도착지점까지 탐색한 경로의 거리의 순차를 구할수없다.BF.. [Leetcode] 787번 - k 경유지 내 가장 저렴한 항공권 1. 문제 파악문제 링크: https://leetcode.com/problems/cheapest-flights-within-k-stops/description/문제 정의: 시작점부터 도착지점까지 k개의 정점을 거쳐서 가는 최단 거리를 구해라.문제의 제약 파악 (입력값 크기, 상수 조건)1 2. 문제 풀이1. 핵심 문제 풀이 도출(문제 의도 파악): 어떻게 하면 시간 복잡도 내로 줄일수 있을까?일단, 이문제는 최단 경로를 구하는 문제이다. 일반적인 최단 경로 문제는 다익스트라 알고리즘을 쓰는 것이 좋지만 이문제는 조건이 있다. 주어진 k개 만큼만 정점 이동이 가능하단 점이다. BFS로 탐색은 방문 정점의 다음 레벨(깊이)의 인접한 정점들 중에서 가장 비용이 적은 정점까지의 거리를 업데이트 하면서 움직일수있.. [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 다음