프로그래머스 배달 자바/Java

프로그래머스 배달 자바/Java

문제 보러가기

코드

인접 행렬을 이용한 풀이

class Solution { private int min(int a, int b){ if (a 아직 방문하지 않음, true -> 이미 방문 for(int i = 0; i < N; i++){ // dist, visited 배열 초기화 dist[i] = graph[0][i]; visited[i] = false; } visited[0] = true; for(int i = 0; i < N-2; i++){ // N-2개의 마을을 방문하는 동안 반복(1번과 마지막 마을 제외) int min = 500001; int idx = 0; // 1번 마을에서 방문하지 않은 마을 중 가장 비용이 적은 마을 번호를 탐색 for(int j = 1; j < N; j++){ if(dist[j] < min && !visited[j]){ min = dist[j]; idx = j; } } visited[idx] = true; for(int j = 1; j < N; j++){ if(dist[j] > dist[idx] + graph[idx][j]){ dist[j] = dist[idx] + graph[idx][j]; } } } for(int D : dist){ if(D <= K) answer++; } return answer; } }

인접 리스트를 이용한 풀이(추가예정)

설명

다익스트라(Dijkstra) 알고리즘을 적용하여 풀 수 있었다.

다익스트라 알고리즘 개념 설명 (추가예정)

from http://nooblette.tistory.com/284 by ccl(A) rewrite - 2021-12-19 02:02:12