프로그래머스 배달 JAVA

코딩테스트 연습 - 배달

문제

해당 문제는 마을별로 연결 정보가 주어졌을 때 1번 마을에서 각 마을까지 이동 거리가 K값 이하인 마을을 구하는 문제다.

단 1번 마을도 포함하여 카운트를 해주어야 한다.

조건

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a!= b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는 데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을 간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

풀이

해당 문제는 bfs를 이용하여 해결했다. 마을 간의 연결 정보는 어레이 리스트 배열을 이용해 담아주었고, 최초 1번에서 갈 수 있는 모든 마을을 큐에 담고 bfs를 돌려주면 된다.

처음에는 기저 조건을 방문 여부 즉 0이 아니면 방문하는 방식으로 했더니 테케에서 반 정도 솔을 할 수 있었고, 생각을 해보니 해당 문제에서는 이동할 때마다 증가하는 값이 마을별로 다르기 때문에 마을에 대해 max값으로 초기화를 한 뒤 이동하려는 마을이 클 경우에만 방문하는 방식으로 해결할 수 있었다.

코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
	    public static int solution(int N, int[][] road, int K) {
        int answer = 1; // 1번마을 무조건 갈수있음
        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
        	list.add(new ArrayList<>());
		}
        
        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]));
		}
        
        Queue<Node> q = new LinkedList<>();
        int[] visit = new int[N+1];
        for (int i = 2; i < visit.length; i++) {
        	visit[i] = Integer.MAX_VALUE; // 방문 배열을 모두 max 값으로 갱신
		}
        q.addAll(list.get(1)); // 1번 마을에서 갈수있는 마을 정보 모두 큐에 담음
        
        while(!q.isEmpty()) { // bfs 돌림
        	Node n = q.poll();
        	if(visit[n.x] <= visit[n.y] + n.v)
        		continue;
        	visit[n.x] = visit[n.y] + n.v;
        	q.addAll(list.get(n.x));
        }
        
        for (int i = 2; i < visit.length; i++) {
			if(visit[i] <= K)
				answer++;
		}
        return answer;
    }
    
	static class Node{
    	int y, x, v;
    	Node(int y, int x, int v){
    		this.y = y;
    		this.x = x;
    		this.v = v;
    	}
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드