[Algorism/HackerRank] Roads and Libraries

black-mins·2021년 4월 6일
0

👉 문제 링크

✏️ 문제 요약

  • 모든 도시에서 방문할 수 있는 도서관을 최소 비용으로 지어야함
  • 비용은 크게 도서관 건설 비용, 도시를 연결하는 도로 비용 2가지 존재
  • 연결이 가능한 도시 목록을 가지고 있음
  • 도서관 건설 최소 비용에 따라 도시별로 도로는 연결될 수도 있고, 아닐수도 있음

💡 문제 풀이

  • 도서관 건설 비용 <= 도로 연결 비용인 경우

    도로 연결 비용보다 도서관 건설 비용이 저렴한 경우에는 각 도시별로 도서관을 짓는게 최소 비용

  • 도서관 건설 비용 > 도로 연결 비용인 경우

    특정 한 도시에 도서관을 짓고, 연결할 수 있는 모든 도시의 도로를 연결
    1개의 도로로 2개의 도시를 연결 할 수 있으므로, 2개의 도시를 연결한 경우 1개의 도로 건설 비용만 부가

  • 자료구조

    구현 코드에서는 모든 연결된 도시의 경우의 수를 파악하기 위해 그래프 사용

💻 구현 코드

  • 리스트를 활용한 그래프 사용
  • 그래프 탐색 방법으로는 DFS를 재귀로 구현
  • 모든 도시는 단 1번만 방문하므로, 도시별 방문 횟수는 결국 도시별 도서관 수 or 도시간의 연결하는 도로의 개수를 구하는데 사용함
코드 보기
  // 도서관 건설 최소 비용을 구함
  static long roadsAndLibraries(int n, int c_lib, int c_road, int[][] cities) {
      List<ArrayList<Integer>> roadGraph = initRoadGraph(n, cities);
      boolean[] visited = new boolean[n];

      long totalCost = 0;

      for (int i = 0; i < roadGraph.size(); i++) {
          if (!visited[i]) {
              if (c_lib > c_road) {
                  totalCost += c_lib + (c_road * (countNumberOfVisitsByDfs(i, visited, roadGraph) - 1));
              } else {
                  totalCost += c_lib * countNumberOfVisitsByDfs(i, visited, roadGraph);
              }
          }
      }

      return totalCost;
  }

  // 도시간 연결하는 그래프
  static List<ArrayList<Integer>> initRoadGraph(int n, int[][] cities) {
      List<ArrayList<Integer>> roadGraph = new ArrayList<>();

      for (int i = 0; i < n; i++) {
          roadGraph.add(new ArrayList<>());
      }

      for (int i = 0; i < cities.length; i++) {
          roadGraph.get(cities[i][0] - 1).add(cities[i][1] - 1);
          roadGraph.get(cities[i][1] - 1).add(cities[i][0] - 1);
      }

      return roadGraph;
  }

  // 도시별 방문 횟수
  static long countNumberOfVisitsByDfs(int index, boolean[] visited, List<ArrayList<Integer>> roadGraph) {
      long cityVisitCount = 1;
      visited[index] = true;

      for (int i = 0; i < roadGraph.get(index).size(); i++) {
          if (!visited[roadGraph.get(index).get(i)]) {
              cityVisitCount += countNumberOfVisitsByDfs(roadGraph.get(index).get(i), visited, roadGraph);
          }
      }

      return cityVisitCount;
  }

0개의 댓글