알고리즘/programmers

프로그래머스 레벨2 배달 (JAVA)

dev-jo 2021. 7. 31. 16:49

오랜만에 글을 씁니다.

 

요즘 프로젝트를 생각하느라 알고리즘은 푸는데 

 

글을 쓸 시간이 없어서 주말에 씁니다!

 

이번 문제는 프로그래머스 레벨2 배달입니다.

 

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

 

코딩테스트 연습 - 배달

5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4

programmers.co.kr

 

 

코드는 GitHub 에도 올라가 있습니다.

 

 

import java.util.LinkedList;
import java.util.Queue;
class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        boolean[] counts = new boolean[N + 1];
        int[] edge = new int[N + 1]; // 거리

        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        counts[1] = true;

        while (!queue.isEmpty()) {

            int x = queue.poll(); // 노드뽑기

            for (int i = 0; i < road.length; i++) { // node 예시 노드,노드,거리
                if (road[i][0] == x) { //현재 노드와 같은지 검사
                    int node = road[i][1]; // 연결된 노드를  뽑음
                    int nodeEdge = road[i][2];
                    int length = edge[x] + nodeEdge; // 이전노드 + 현재 노드까지 거리
                    if (length <= edge[node] || edge[node] == 0) {
                        edge[node] = length;
                        if(!counts[node] && edge[node] <= K) { // 카운트 된적이 없고 K 보다 같거나 작을때
                            counts[node] = true;
                        }
                        queue.add(node);
                    }


                } else if (road[i][1] == x) { //앞뒤로 검사해줌 , 위랑 반대로 뽑음
                    int node = road[i][0];
                    int nodeEdge = road[i][2];
                    int length = edge[x] + nodeEdge; // 이전노드 + 현재 노드까지 거리
                    if (length <= edge[node] || edge[node] == 0) {
                        edge[node] = length;
                        if(!counts[node] && edge[node] <= K) { // 카운트 된적이 없고 K 보다 같거나 작을때
                            counts[node] = true;
                        }
                        queue.add(node);
                    }
                }
            }

        }

        for(int i=1; i<counts.length; i++) {
            if(counts[i]) {
                answer++;
            }
        }

        return answer;
    }
}

 

 

평범하게 BFS로 탐색하는데

 

이문제는 주의 해야 할 게 있다

 

일단 기본적으로 탐색이 안되어 있을 때는 무조건 추가를 해주고

 

탐색이 되어 있을 경우에

 

현재 노드까지의 걸이가 기존에 탐색된 거리보다 짧다면

 

재 탐색을 하기 위해 큐에 넣어준다.

 

기존에 탐색한 거리가 4이고

 

이번 탐색한게 3일 경우 다시 탐색해주는 거다..

 

 

기본적으로 BFS DFS를 알고 있다면..

 

그렇게 어려운 문제는 아닙니다.

 

조금만 생각하면 금방 풀 수 있는 문제였습니다.