[PGM_12978] 배달 (java)

문제링크

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

코딩테스트 연습 - 배달

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 구현

1. 문제 이해

주어지는 파라미터로 정수인 N과 K 그리고 int형 이차원 배열 road가 주어진다.

N은 마을의 개수 K는 특정 임계값 그리고 road는 마을과 마을 사이의 길에 대한 정보가 들어있는 배열이다.

road의 첫번째 값은 첫번째 마을, 두번째 값은 두번째 마을 마지막으로 세번째 값은 그 두 마을을 잇는 길의 거리이다.

두 마을을 잇는 경우는 여러개 일 수 있다.

 

1번 마을에서 시작하여 길을 찾아갈 때 거리가 임계값 K 이하로 갈 수 있는 모든 마을을 구해주는 문제이다.

 

2. 접근방법

1. 길에 대한 정보로 마을에 대한 지도를 만들어준다.

- 길은 최단거리의 길 하나만 만들어준다.

2. 지도를 활용하여 1번 마을로부터 떨어진 거리를 모두 구해준다.

- 재귀를 사용하여 구해준다.

- 특정 마을에서 갈 수 있는 모든 마을을 확인하고 만약 더 짧은 거리로 갈 수 있다면 그 마을과 떨어진 거리를 짧은 거리로 변경하고 들어가서 재귀로 다시 모든 마을에 대하여 점검한다.

3. 구해준 거리를 활용해 K 이하의 모든 마을을 확인하여준다.

 

3. 구현코드 설명

- 마을 이어주기

public void connectRoad(int[][] road, Map<Village, Integer> map) {
    for (int i = 0; i < road.length; i++) {
        int vilA = road[i][0];
        int vilB = road[i][1];
        int weight = road[i][2];

        Village forward = new Village(vilA, vilB);
        Village reverse = new Village(vilB, vilA);

        if (map.containsKey(forward)) {
            weight = map.get(forward) < weight ? map.get(forward) : weight;
        }
        map.put(forward, weight);
        map.put(reverse, weight);
    }
}

마을을 이어주기 위하여 마을 두개를 가지고 있는 클래스 하나를 정의하였다.(두 마을에 대한 좌표 비교를 위해)

두개의 마을에 대한 좌표를 정해주기 위해 equals를 재정의해주어 vilA와 vilB가 각각 어디인지 확인해주도록 하여 같은지 판단하게 한다.

(vilA,vilB)와 (vilB,vilA)로 양방향 연결을 해준다.

가중치 값은 만약 기존 map에 포함되어있었다면 현재 가지고 있는 가중치와 비교해 최소값을 넣어주면 된다.

 

- 마을A와 떨어진 최단 거리 찾기

public void findShortestDistanceByA(Map<Village, Integer> map, int[] distance, int now, int N) {
    for (int i = 1; i <= N; i++) {
        Village village = new Village(now, i);
        if (!map.containsKey(village))
            continue;
        Integer weight = map.get(village);
        if (distance[i] > distance[now] + weight || distance[i] == -1) {
            distance[i] = distance[now] + weight;
            findShortestDistanceByA(map, distance, i, N);
        }
    }
}

마을 A와 떨어진 최단 거리를 찾아주는 코드이다.

붙어있는 모든 마을들을 확인해주게 된다.

만약 붙어있는 마을의 최단거리가 현재 A에서 자신의 위치까지 떨어진 거리 distance[now]와 weight를 합한 값보다 작다면 다시 재귀를 활용하여 그 마을과 관련된 모든 길을 확인해주어야한다.

구현코드

package pgm_12978;

import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Solution {
    public int solution(int N, int[][] road, int K) {
        Map<Village, Integer> map = new HashMap<>();
        int[] distance = new int[N + 1];
        for (int i = 2; i < N + 1; i++)
            distance[i] = -1;

        connectRoad(road, map);
        findShortestDistanceByA(map, distance, 1, N);

        int count = 0;
        for (int i = 1; i < N + 1; i++)
            if (distance[i] != -1 && distance[i] <= K)
                count++;
        return count;
    }

    public void connectRoad(int[][] road, Map<Village, Integer> map) {
        for (int i = 0; i < road.length; i++) {
            int vilA = road[i][0];
            int vilB = road[i][1];
            int weight = road[i][2];

            Village forward = new Village(vilA, vilB);
            Village reverse = new Village(vilB, vilA);

            if (map.containsKey(forward)) {
                weight = map.get(forward) < weight ? map.get(forward) : weight;
            }
            map.put(forward, weight);
            map.put(reverse, weight);
        }
    }

    public void findShortestDistanceByA(Map<Village, Integer> map, int[] distance, int now, int N) {
        for (int i = 1; i <= N; i++) {
            Village village = new Village(now, i);
            if (!map.containsKey(village))
                continue;
            Integer weight = map.get(village);
            if (distance[i] > distance[now] + weight || distance[i] == -1) {
                distance[i] = distance[now] + weight;
                findShortestDistanceByA(map, distance, i, N);
            }
        }
    }


    public class Village {
        private int vilA;
        private int vilB;

        public Village(int vilA, int vilB) {
            this.vilA = vilA;
            this.vilB = vilB;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Village village = (Village) o;
            return vilA == village.vilA && vilB == village.vilB;
        }

        @Override
        public int hashCode() {
            return Objects.hash(vilA, vilB);
        }
    }
}

 

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)