배달 (그래프, DFS)

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

프로그래머스

 

문제 풀이

가중치 있는 그래프의 구현 및 경로 탐색 문제이다. BFS는 가중치가 없는 경로를 찾는데 좋다고 해서 DFS로 풀었는데, 다른 사람들은 BFS로 많이들 풀었다. 그 이외 플로이드, 다익스트라 같은 알고리즘도 언급되었는데, 이에 대해서도 공부를 해봐야 겠다.

 

 

작성한 코드 (정답)

import java.util.*;

class Solution {

    public class Road {
        int to;
        int time;

        public Road(int to, int time) {
            this.to = to;
            this.time = time;
        }
    }

    public int solution(int N, int[][] road, int K) {

        List<List<Road>> graph = new ArrayList<>();
        Set<Integer> result = new HashSet<>();

        for (int i = 0; i < N+1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int[] inner : road) {
            graph.get(inner[0]).add(new Road(inner[1], inner[2]));
            graph.get(inner[1]).add(new Road(inner[0], inner[2]));
        }

        boolean[] visited = new boolean[N+1];

        dfs(K, 1, graph, visited, result, 0);

        return result.size();
    }

    public void dfs (int K, int startNode, List<List<Road>> graph, boolean[] visited, Set<Integer> result, int totalTime) {

        result.add(startNode);
        visited[startNode] = true;

        for (Road road : graph.get(startNode)) {

            if (!visited[road.to] && totalTime + road.time <= K) {
                dfs(K, road.to, graph, visited, result, totalTime+road.time);
            }
        }
        
        visited[startNode] = false;
    }
}