[Java] Summer/Winter Coding(~2018) - 배달 (Lv 2)

https://school.programmers.co.kr/learn/courses/30/lessons/12978

프로그래머스

 

 

✔ 입출력 예시

배달 입출력 예시

 

 

💡 포인트

1️⃣ 모든 마을을 연결하는 도로는 양방향

2️⃣ 1번 마을의 음식점으로부터 K시간 이하로 배달이 가능한 마을에서만 주문을 받음

3️⃣ road {a, b, c} 👉 {a 마을, b 마을, a와 b 사이에 있는 도로를 지나는데 걸리는 시간}

4️⃣ 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있음

5️⃣ 임의의 두 마을 간에는 항상 이동 가능한 경로가 존재 👉 하나의 마을은 하나 이상의 마을과 반드시 연결

 

 

❓ 풀이과정

1️⃣ 변수 및 배열 선언

2️⃣ 양방향 거리 체크

3️⃣ 모든 인덱스 거리 배열 무제한, 1번 마을 이동거리 0 초기화

4️⃣ while문을 멈추기 위한 cnt (마지막 노드를 제외한 모든 노드 탐색한 경우 while 멈추기)

5️⃣ 방문하지 않은 마을 중 가장 최소한의 거리로 방문할 수 있는 마을 pick

6️⃣ 현재 방문한 마을로부터 각 이어진 마을에 대해 최소한의 길이 구하기

7️⃣ while문의 종료될때까지 5️⃣~6️⃣ 반복

8️⃣ 1번 ~ 각 마을까지의 길이 배열 중 K이하인 마을 수 세기

 

 

❗ 실행 결과

👉 테스트 통과

 

 

✔ 소스 코드

package lv2;

import java.util.Arrays;

public class Solution {  // 배달

	private int solution(int N, int[][]road, int K) {
    	// 1️⃣
		final int INF = 987654321;

		int answer = 0;
		
		int[] dist = new int[N+1];
		int[][] adj = new int[N+1][N+1];
		boolean[] v = new boolean[N+1];
		
		// 2️⃣ 
		for (int i = 1; i < adj.length; i++) {
			Arrays.fill(adj[i], INF);
			adj[i][i] = 0;
		}
		for (int i = 0; i < road.length; i++) {
			if(adj[road[i][0]][road[i][1]] == INF) {
				adj[road[i][0]][road[i][1]] = road[i][2];
				adj[road[i][1]][road[i][0]] = road[i][2];
			} else {
				adj[road[i][0]][road[i][1]] = Math.min(adj[road[i][0]][road[i][1]], road[i][2]);
				adj[road[i][1]][road[i][0]] = Math.min(adj[road[i][1]][road[i][0]], road[i][2]);
			}
		}
		
		/*for (int i = 1; i < adj.length; i++) {
			System.out.println(Arrays.toString(adj[i]));
		}*/
		
        // 3️⃣
		Arrays.fill(dist, INF);
		dist[1] = 0;
		
        // 4️⃣
		int cnt = 0;
		while(cnt < N-1) {
//			System.out.println("while문");
			int min = INF;  // 최소값을 비교하기 위해 무제한을 담은 최소값 변수 선언
			int node = 0;  // 가장 탐색하지 않은 마을 중 가장 최소한의 거리에 있는 마을 번호를 담을 변수
			
            // 5️⃣
			for (int i = 1; i < dist.length; i++) {
				if(!v[i] && dist[i] < min) {
					min = dist[i];
					node = i;
				}
			}
            cnt++;
			v[node] = true;
//			System.out.println(Arrays.toString(dist));
			
			
            // 6️⃣
			for (int i = 1; i < adj.length; i++) {
				if(!v[i] && adj[node][i] != INF && dist[i] > dist[node] + adj[node][i]) {
					dist[i] = dist[node] + adj[node][i];
				}
			}
//			System.out.println(Arrays.toString(dist));
		}
		
        // 8️⃣
		for (int i = 1; i < dist.length; i++) {
			if(dist[i] <= K) {
				answer++;
			}
		}
		
		return answer;
	}
	
	public static void main(String[] args) {
		Solution delivery = new Solution();
		
		/*int N = 5;
		int[][] road = {{1, 2, 1}, {2, 3, 3}, {5, 2, 2}, {1, 4, 2}, {5, 3, 1}, {5, 4, 2}};
		int K = 3*/;
		int N = 6;
		int[][] road = {{1, 2, 1}, {1, 3, 2}, {2, 3, 2}, {3, 4, 3}, {3, 5, 2}, {3, 5, 3}, {5, 6, 1}};
		int K = 4;
		
		System.out.println(delivery.solution(N, road, K));
	}

}

 

처음 문제 풀이 시 a, b 사이의 도로가 여러개 있을 수 있다는 설명을 놓쳐 계속 삽질을 했어야 했던 문제였다😢

잊어갈때쯤 다시 풀어볼 문제로 Pick!