프로그래머스 - 배달

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

코딩테스트 연습 - 배달

 

 

 

 

 

얼마전에 풀었던 '가장 먼 노드' 문제(https://programmingiraffe.tistory.com/30)와 비슷하다고 생각해서 bfs로 풀었다. 그런데 채점을 돌리면 50%의 테스트케이스만 통과한다.

 

'가장 먼 노드' 문제에서는 모든 노드의 가중치가 1이었는데, 이 문제에서는 가중치가 달라 거쳐가는 경우 최소값을 갱신해줘야하는데 안되는 것 같다..

 

결국 더 복잡하지만 다익스트라 알고리즘으로 풀어줘야 한다.

 

 

 

 

 

BFS로 푼 풀이(모든 tc 통과 X)

import java.util.*;

class Solution {
    static final int INF = 50000001;
    static int[][] graph;
    static boolean[] visited;
    static int[] dist;
    
    public int solution(int N, int[][] road, int K) {
        graph = new int[N + 1][N + 1];
        for(int a[] : graph) {
            Arrays.fill(a, INF);
        }
        
        visited = new boolean[N + 1];
        
        dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        for(int i = 0; i < road.length; i++) {
            int a = road[i][0];
            int b = road[i][1];
            int c = road[i][2];
            
            graph[a][b] = Math.min(graph[a][b], c);
            graph[b][a] = Math.min(graph[b][a], c);
        }
        
        bfs(1);
        
        int answer = 0;
        for(int i = 1; i < N + 1; i++) {
            if(dist[i] <= K) {
                answer++;
            }
        }

        return answer;
    }
    
    public void bfs(int v) {
        Queue<Integer> q = new LinkedList<>();
        
        q.add(v);
        visited[v] = true;
        dist[1] = 0;
        
        while(!q.isEmpty()) {
            int p = q.poll();
            
            for(int i = 1; i < graph.length; i++) {
                if(graph[p][i] != INF && !visited[i]) {
                    q.offer(i);
                    visited[i] = true;
                    dist[i] = Math.min(dist[i], dist[p] + graph[p][i]);
                }
            }
        }
    }
}

 

 

 

 

 

다익스트라 알고리즘

import java.util.*;

class Node implements Comparable<Node> {
    int to;
    int weight;
    
    Node(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Node o) {
		return Integer.compare(this.weight, o.weight);
	}
}

class Solution {
    static List<Node>[] list;
    static boolean[] visited;
    static int[] dist;
    
    public int solution(int N, int[][] road, int K) {
        list = new ArrayList[N + 1];
        for(int i = 1; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }
        
        visited = new boolean[N + 1];
        
        dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        
        for(int i = 0; i < road.length; i++) {
            int a = road[i][0];
            int b = road[i][1];
            int c = road[i][2];
            
            list[a].add(new Node(b,c));
			list[b].add(new Node(a,c));
        }
        
        dijkstra(1);
        
        int answer = 0;
        for(int i = 1; i < N + 1; i++) {
            if(dist[i] <= K) {
                answer++;
            }
        }

        return answer;
    }
    
    public void dijkstra(int start) {
        Queue<Node> q = new PriorityQueue<>();
        
        q.add(new Node(start,0));
        dist[start] = 0;
        
        while(!q.isEmpty()) {
            Node node = q.poll();
            int to = node.to;
            
            if(visited[to]) {
                continue;
            } else {
                visited[to] = true;
            } 
            
            for(Node next : list[to]) {
				if(dist[next.to]  >= dist[to] + next.weight) {
					dist[next.to] = dist[to] + next.weight;
					q.add(new Node(next.to, dist[next.to]));
				}
			}
        }
    }
}

 

 

 

 

 

 

참고

다익스트라 알고리즘 https://loosie.tistory.com/146