(Java) 프로그래머스 - 배달

문제를 읽고 최단거리를 탐색하는 내용이기에

BFS로 해결할 수 있을줄 알았는데 많은 어려움을 겪었다.

 

BFS 코드를 작성하다가 검색을 통해 힌트를 얻었고

다익스트라나 플로이드 와샬을 사용할 수 있다는 것을 알아서 모든 방법으로 풀어봤다.

다익스트라와 플로이드 와샬은 처음 배우는 알고리즘이여서 어려웠다.

이 문제는 하나의 정점에서 다른 정점들의 최단 거리임으로 다익스트라로 접근하는것이 가장 맞는것 같다.

 

다익스트라와 플로이드 와샬을 모른다면 잘 정리해놓은 다른분의 블로그를 첨부한다.

[알고리즘/ 그래프] 다익스트라(Dijkstra) vs 플로이드 와샬(Floyd Warshall) (JAVA)

---

최종 코드(BFS)

class Solution {
	static List<ArrayList<Node>> list;
    static int cnt;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        // 자기 자신의 마을은 무조건 방문
        cnt = 1;

        // 인접 리스트
        list = new ArrayList<>();
        int[] visited = new int[n + 1];

        // 리스트 초기화
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        // 인전 리스트를 통해 Node에 값 입력
        for (int i = 0; i < road.length; i++) {
            list.get(road[i][0]).add(new Node(road[i][0], road[i][1], road[i][2]));
            list.get(road[i][1]).add(new Node(road[i][1], road[i][0], road[i][2]));
        }

        // BFS 탐색
        bfs(n, k, visited);

        answer = cnt;

        return answer;
    }
    // BFS 탐색 메서드
    static void bfs(int n, int k, int[] visited) {
        // 탐색을 위한 queue
        Queue<Node> queue = new LinkedList<>();

        // 방문 배열 최댓값으로 초기화
        for (int i = 2; i < visited.length; i++) {
            visited[i] = Integer.MAX_VALUE;
        }
        // 1번에서 갈수있는 마을 전부 추가
        queue.addAll(list.get(1));

        // BFS
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            // 방문 예정 마을이 이동거리의 합 보다 크거나 같지 않으면
            if(!(visited[node.b] <= visited[node.a] + node.l)) {
                visited[node.b] = visited[node.a] + node.l;
                queue.addAll(list.get(node.b));
            }
        }

        // 출력
        for (int i = 2; i < n + 1; i++) {
            if(visited[i] <= k) {
                cnt++;
            }
        }
    }

    // Node 클래스
    static class Node {
        int a, b, l;

        Node(int a, int b, int l) {
            this.a = a;
            this.b = b;
            this.l = l;
        }

        // 클래스 출력 메서드
        @Override
        public java.lang.String toString() {
            return "Node{" +
                    "a=" + a +
                    ", b=" + b +
                    ", l=" + l +
                    '}';
        }
    }
}

 

최종 코드(다익스트라)

class Solution {
	static int cnt;
    static int[][] arr;
    static int[] dist;
    static boolean[] visited;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        cnt = 0;
        arr = new int[n + 1][n + 1];

        // 인접 행렬 초기화
        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                arr[i][j] = 500001;
            }
        }

        // 인접행렬 거리값 삽입
        for (int i = 0; i < road.length; i++) {
            if(arr[road[i][0]][road[i][1]] > road[i][2]) {
                arr[road[i][0]][road[i][1]] = road[i][2];
                arr[road[i][1]][road[i][0]] = road[i][2];
            }
        }

        // 거리, 방문 배열 만들기
        dist = new int[n + 1];
        // 최댓값으로 초기화
        for (int i = 2; i < n + 1; i++) {
            dist[i] = 500001;
        }
        visited = new boolean[n + 1];
        // 첫번째 마을 체크
        visited[1] = true;

        // 다익스트라 메서드 호출
        dijkstra(n, k);

        int answer = cnt;
        return answer;
    }
    // 다익스트라 메서드
    static void dijkstra(int n, int k) {
        // 0 ~ n-1 or 1 ~ n 까지 반복
        for (int i = 1; i < n; i++) {
            int min = 500001;
            int idx = 1;

            // 가장 작은 거리애 있는 인덱스값 찾기
            for (int j = 2; j <= n; j++) {
                if(!visited[j] && min > dist[j]) {
                    idx = j;
                    min = dist[j];
                }
            }

            // 방문 체크
            visited[idx] = true;

            // 돌아가는 루트가 더 빠른지 탐색
            for (int j = 2; j <= n ; j++) {
                if(dist[j] > dist[idx] + arr[idx][j]) {
                    dist[j] = dist[idx] + arr[idx][j];
                }
            }
        }

        // k 이하의 값 카운트
        for (int i = 1; i <= n ; i++) {
            if(dist[i] <= k) {
                cnt++;
            }
        }
    }
}

 

최종 코드(플로이드 와샬)

class Solution {
    public int solution(int N, int[][] road, int K) {
        int answer = 0;

        // 플로이드 와셜 알고리즘을 위한 2차원 배열
        int[][] arr = new int[N][N];

        // 최댓값으로 배열 초기화
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if(i == j) {
                    continue;
                }
                arr[i][j] = 500001;
            }
        }

        // 배열 인덱스를 0부터 하기위해 -1 뺴주고 인접 행렬 만들기
        for (int i = 0; i < road.length; i++) {
            // 새로 입력되는 거리가 더 크면 무시
            if(arr[road[i][0] - 1][road[i][1] - 1] >= road[i][2]) {
            arr[road[i][0] - 1][road[i][1] - 1] = road[i][2];
            arr[road[i][1] - 1][road[i][0] - 1] = road[i][2];
            }
        }

        // 플로이드 와샬
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    // jk를 바로 가는것과 i를 거쳐서 가는것중 i를 거쳐서 가는게 더 빠를 경우
                    if(arr[j][k] > arr[j][i] + arr[i][k]) {
                        arr[j][k] = arr[j][i] + arr[i][k];
                    }
                }
            }
        }

        // 출력
        for (int i = 0; i < N; i++) {
            if(arr[0][i] <= K) {
                answer++;
            }
        }
        return answer;
    }
}