Problem1

문제 설명

- 각 섬(=노드) 사이를 자전거 타고 활보한다. k 시간에 정차 할 수 있는 섬들은?

- 간선의 값은 이동거리를 의미한다.

- 섬은 중복해서 이동할 수 있다.

- 시작 노드는 0 이다.

 

---

입출력 정보

Input

- int n(노드의 수): 0~n-1까지 노드가 존재

- int k(도착시간)

- int[][] roads(간선 정보)

int[][] roads={{5, 4, 6}, {5, 2, 5}, {0, 4, 2}, {2, 3, 3}, {1, 2, 7}, {0, 1, 3}};
//roads[0]= {5,4,6};
//노드 5와 노드 4 사이 간선의 길이는 6

 

Output

- int[] answer(k 시간에 도착할 수 있는 노드들의 집합)

---

Code

Solution2.class

package jason.socar.problem1;

import java.util.ArrayList;
import java.util.List;

public class Solution2 {

    public int[] solution(int n, int k, int[][] roads) {
        int[][] graph=new int[n][n];
        boolean[][] visited=new boolean[k+1][n];
        List<Integer>[]dp= new ArrayList[k+1];
        for(int i=0;i<k+1;i++){
            dp[i]=new ArrayList<>();
        }
        dp[0].add(0);

        for(int[] road: roads){
            int n1=road[0];
            int n2=road[1];
            int len=road[2];

            graph[n1][n2]=len;
            graph[n2][n1]=len;

        }

        int cur_time=0;

        while(cur_time<k){
            for(Integer node: dp[cur_time]){
                for(int i=0;i<n;i++){
                    if(graph[node][i]!=0){
                        int value= cur_time+graph[node][i];
                        if(value<=k && !visited[value][i]){
                            visited[value][i]=true;
                            dp[value].add(i);
                        }

                    }
                }
            }
            cur_time+=1;

        }
        if(dp[k].isEmpty())
            return new int[]{-1};

        return dp[k].stream()
                .mapToInt(i->i)
                .toArray();
    }
}

 

Problem1.class

package jason.socar.problem1;

import java.util.Arrays;

public class Problem1 {

    public static void main(String[] args) {
        int n=6;
        int k=17;

        int[][] roads={{5, 4, 6}, {5, 2, 5}, {0, 4, 2}, {2, 3, 3}, {1, 2, 7}, {0, 1, 3}};
//        int[][] roads={{0, 1, 2}, {1, 2, 7}, {2, 3, 10}, {3, 0, 9}};

        int[] answer=new Solution2().solution(n,k,roads);
        System.out.println(Arrays.toString(answer));
    }
}

---

핵심

List<Integer>[]dp= new ArrayList[k+1];
		//이 과정이 꼭 있어야 한다.
        for(int i=0;i<k+1;i++){
            dp[i]=new ArrayList<>();
        }
        //0초에 도착하는 노드는 노드 0뿐이다.
        dp[0].add(0);

 

//시간을 기준으로!
while(cur_time<k){
            for(Integer node: dp[cur_time]){
                for(int i=0;i<n;i++){
                    if(graph[node][i]!=0){
                        int value= cur_time+graph[node][i];
                        if(value<=k && !visited[value][i]){
                            visited[value][i]=true;
                            dp[value].add(i);
                        }

                    }
                }
            }
            cur_time+=1;

        }