개발자 김수진

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 해당 문제는 하나의 정점에서 다른 정점들까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용해 풀었다. map이라는 벡터 배열을 선언하여 각 정점마다 인접한 정점까지의 거리를 가지고 있도로 했다. 또한 1번 정점부터 다른 정점들까지의 거리를 구하기 저장하기 위해 dist 변수를 선언하고 정점의 개수만큼 1e9로 초 기화했다. 다음으로 dijkstra 함수에서는 prior..

[개념] 다익스트라 알고리즘이란 하나의 정점에서부터 다른 정점들까지의 최단거리를 구하는데 사용되는 탐색 알고리즘이다. 정점까지의 최단 경로를 구할 때 , 이전에 구한 다른 정점들까지의 최단 경로를 구한다. 1. 출발 정점을 구한다 2. 출발 정점과 인접한 점들을 방문 처리한다. 3. 출발 정점과 인접한 점들 중에서 비용이 가장 적은 정점으로 간다. 4. 다음 정점에서 마찬가지로 2,3번을 반복한다. 위의 과정을 반복할 때 한번 방문했던 정점은 재방문 하지않는다. 3번의 과정을 통해 최단 경로를 보장할 수 있다. 현재 정점을 기준으로 비용이 가장 적은 정점으로 가므로 이것이 최단 경로가 되는 것이다. 위의 그래프를 기준으로 각 정점들의 거리를 배열에 초기화하면 다음과 같이 된다. 1 2 3 4 5 6 1 ..