문제1

문제 설명

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

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

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

- 시작 노드는 0 이다.

 

입출력 정보

Input

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

- int k(도착시간)

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

Output

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

 

Code

import java.util.*;

class Solution {
	
    public int[] solution(int n, int k, int[][] roads) {
        int[] answer = {};

        int[][] graph = new int[n][n];
        int[][] visited = new int[k+1][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]은 노드 0밖에 존재하지 않는다.
        dp[0].add(0);


        for(int i=0; i<roads.length; i++) {
            int v1 = roads[i][0];
            int v2 = roads[i][1];
            graph[v1][v2] = roads[i][2];
            graph[v2][v1] = roads[i][2];
        }

        int time = 0;
        while(time < k) {
            for(int i=0; i<dp[time].size(); i++) {
                for(int j=0; j<n; j++) {
                    if(graph[dp[time].get(i)][j] != 0) {
                        int val = time + graph[dp[time].get(i)][j];
                        if(visited[dp[time].get(i)][j] == 0 && val <= k) {
                            visited[val][i] = 1;
                            dp[val].add(j);
//                            System.out.println("time is \"" + time + "\" now visited [" + j + "]");
                        }
                    }
                }
            }
            time++;
        }

//        for(int i=0; i<dp.length; i++) {
//            System.out.print("dp[" + i + "] :: ");
//            for(Integer node : dp[i]) {
//                System.out.print(node + " ");
//            }
//            System.out.println();
//        }

        answer = new int[dp[k].size()];

        if(!dp[k].isEmpty()) {
            for(int i=0; i<dp[k].size(); i++) {
                answer[i] = dp[k].get(i);
            }
            Arrays.sort(answer);
        } else {
            answer = new int[1];
            answer[0] = -1;
        }
//        if(dp[k].isEmpty()) {
//            return new int[]{-1};
//        }
//
//        return dp[k].stream().mapToInt(i->i).toArray();
        return answer;
    }
}