배달 [자바]

 

🧫 문제 분석

✔️ 출처

배달 level 2

📖 문제

 

 

거리 값이 존재하는 그래프 문제

이 문제를 통해 다익스트라, 플로이드 워샬 등

거리 값이 존재하는 그래프의 탐색이 얼마나 부족한지 깨달았다.

 

해당 문제를 BFS, 플로이드 워샬, 다익스트라로 풀어보았다. 

그리고 거리가 있는 그래프에 대한 간단한 정리를 할 예정이다. 

 

---

🔅 문제 풀이 - BFS

import java.util.*;

class Solution {
    // N개의 마을, K : 갈 수 있는 거리
    // BFS 탐색으로 K - 각 마을까지의 비용 >= 0 인 곳을 방문
    int[] visited;
    
    public int solution(int N, int[][] road, int K) {
        int[][] graph = new int[N + 1][N + 1]; 
        visited = new int[N + 1];
        
        // 마을 그래프 생성
        for (int i = 0; i < road.length; i++) {
            int start = road[i][0];
            int end = road[i][1];
            
            
            // 양방향, 걸리는 시간 최소값
            graph[start][end] = graph[end][start] 
                = ((graph[start][end] > 0) ? 
                   Math.min(graph[start][end], road[i][2]) : road[i][2]);
        }

        return bfs(graph, K);
    }
    
    private int bfs(int[][] towns, int k) {
        Queue<int[]> q = new LinkedList<>(); // [다음 마을, 남은 k]
        q.add(new int[] {1, 0}); // 문제에서 '1번 마을에 있는 음식점'
        visited[1] = k;
        int count = 1; // 1번 마을도 포함
        
        while(!q.isEmpty()) {
            int[] curTownInfo = q.poll();
            int idx = curTownInfo[0];

            
            // 0이면 더이상 배달할 시간이 없음
            if (curTownInfo[1] == k) continue;
                     
            // 각 연결된 마을들을 순회
            for (int i = 1; i < towns.length; i++) {
                if (towns[idx][i] > 0 
                    && (curTownInfo[1] + towns[idx][i]) <= k) {// 남은 배달시간 안에 가능하다면 
                    
                    // 같은 마을을 가는데 더 비용이 적게 든다면
                    if (visited[i] > curTownInfo[1] + towns[idx][i]) {
                        q.add(new int[] {i, (curTownInfo[1] + towns[idx][i])});
                        visited[i] = curTownInfo[1] + towns[idx][i];
                        
                    } else if (visited[i] == 0) {
                        q.add(new int[] {i, (curTownInfo[1] + towns[idx][i])});
                        visited[i] = curTownInfo[1] + towns[idx][i];
                        count++;
                    }
                }
            }
        }
        return count;
    }
}

🔅 문제 풀이 - 플로이드 워샬

import java.util.*;

class Solution {
    
    final int INF = 100000000;
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int[][] graph = new int[N + 1][N + 1];
        
        
        // 무한으로 채우기
        for (int i = 1; i < N + 1; i++) {
            Arrays.fill(graph[i], INF);
        }
        
        for (int i = 0; i < road.length; i++) {
            int start = road[i][0];
            int end = road[i][1];
            graph[start][end] = graph[end][start] = (graph[start][end] == INF ? road[i][2] : Math.min(graph[start][end], road[i][2]));
        }
        
        
        // a->b 로 가는 거리의 최솟값 찾기 a->b, a->k 로 가고 k->b로 가는 방법 중 최솟값
        for (int k = 1; k < N + 1; k++) {
            graph[k][k] = 0;
            for (int a = 1; a < N + 1; a++) {
                for (int b = 1; b < N + 1; b++) {
                    graph[a][b] = Math.min(graph[a][b] , graph[a][k] + graph[k][b]);
                }
            }
        }
        
        for (int i = 1; i < graph[1].length; i++) {
            answer += (graph[1][i] <= K) ? 1 : 0;
        }
        
        return answer;
    }
}

 

 

🔅 문제 풀이 -  다익스트라

import java.util.*;

class Solution {
    
    class Node {
        int n;
        int cost;
        
        public Node(int n, int cost) {
            this.n = n;
            this.cost = cost;
        }
    }
    
    final int INF = 100000000;
    int[] dist;
    
    public int solution(int N, int[][] road, int K) {
        ArrayList<Node>[] graph = new ArrayList[N + 1]; // 그래프
        dist = new int[N + 1]; // 거리 계산용 
        int answer = 0;
        
        for (int i = 0; i < N + 1; i++) {
            graph[i] = new ArrayList<>();    
        }
        
        // 거리를 우선 무한으로 채우기
        Arrays.fill(dist, INF);
        dist[1] = 0; // 시작 지점은 0
        
        for (int i = 0; i < road.length; i++) {
            int start = road[i][0];
            int end = road[i][1];
            
            graph[start].add(new Node(end, road[i][2]));
            graph[end].add(new Node(start, road[i][2]));            
        }
        
        daijstra(graph);
        
        // 카운팅
        for (int time : dist) {
            answer += time <= K ? 1 : 0;
        }

        return answer;
    }
    
    private void daijstra(ArrayList<Node>[] graph) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1, 0));
        
        while(!q.isEmpty()) {
            Node cur = q.poll();
            
            // 현재 노드 비용이 현재 노드까지의 최단 거리보다 크다면 넘김
            if (cur.cost > dist[cur.n]) continue;
            
            // 현재 노드와 연결된 노드들 처리
            for (Node next : graph[cur.n]) {
                // 다음 노드의 비용 >  현재 노드 비용 + 다음 노드로 가는 비용이라면 최신화
                if (dist[next.n] > cur.cost + next.cost) {
                    dist[next.n] = cur.cost + next.cost;
                    q.add(new Node(next.n, dist[next.n]));
                }
            }
        }
        
    }
}

 

❗ 오답노트 / 필요한 지식

1. 거리 관련 그래프 문제를 오랜만에 풀어서 그런지 또 엄청나게 실수했다. 시간도 많이 걸리고, 잘 안된다면 개념이 부족한 것이 아닌지 생각해보자.