최단경로탐색

📖 문제   프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr   💡  풀이 방식• BFS필요 자료구조- 인접 리스트- 1차원 최단 거리 배열 (destination으로부터의 최단 거리를 나타냄) 1. 인접 리스트 그래프 graph에 길 정보를 저장한다.2. 최단 거리 배열을 모두 최댓값으로 저장한다.3. 시작점 destination부터 BFS를 진행하며 최단 거리 배열을 채운다.for(int next : graph[now]) { if(dist[now] + 1    🔺 코드1. List>를 활용한 풀이123456789101..

📍 종류 1) BFS - 가중치 X / 단순 최단 경로 탐색 2) 다익스트라 - 가중치 O / 한 노드 기준 모든 노드와의 최단 경로 탐색 3) 플로이드-워셜 - 상관 X / 모든 노드 기준 모든 노드 간 최단 경로 탐색 (사실상 그냥 dp) 4) 벨만 - 포드 - 가중치 O / 특정 출발 노드 → 다른 모든 노드까지의 최단 경로 탐색 (참고) [백준 1753] 최단경로 -Java코드 (Dijkstra)★★★ https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘 bangu4.tistory.com