Lv 3. 부대복귀

2024. 11. 19. 17:18·Algorithm & Data Structures/Programers

https://school.programmers.co.kr/learn/courses/30/lessons/132266

 

프로그래머스

SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프

programmers.co.kr

 

 

 

이 문제는 특정 목적지에서 여러 출발지까지의 최소 이동 거리를 구하는 문제다.
주어진 그래프는 양방향 도로로 연결되어 있으며,
BFS를 사용해 목적지로부터 각 노드까지의 거리를 계산한다.

먼저 solution 메서드는 입력으로 주어진 그래프 정보를 graph 리스트 배열로 초기화하고,
각 노드의 거리를 저장할 cost 배열을 -1로 초기화하여 방문 여부와 거리를 동시에 관리한다.
그런 다음, 모든 도로 정보를 읽어 graph에 양방향으로 저장한다.

핵심은 bfs 메서드로, 목적지에서 출발해 각 노드로의 최단 거리를 구한다.
큐를 사용해 BFS를 구현하며, 큐에서 노드를 하나씩 꺼내 해당 노드와 연결된 노드를 탐색한다.
아직 방문하지 않은 노드(cost[num] == -1)는 큐에 추가하고,
현재 노드까지의 거리에서 1을 더한 값을 해당 노드의 거리로 설정한다. 이렇게 하면 최단 거리가 자동으로 계산된다.

최종적으로 각 출발지 노드가 저장된 sources 배열을 순회하며, cost 배열에서 각 노드의 거리를 가져와 결과 배열에 저장한다.
만약 어떤 출발지가 목적지에 도달할 수 없는 경우, 그 값은 초기값인 -1로 유지된다.
마지막으로 결과 배열을 반환해 각 출발지에서 목적지까지의 최소 거리를 반환한다.

 

 

 

import java.util.*;

class Solution {
    
    List<Integer>[] graph;
    int[] cost;
    
    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        graph = new ArrayList[n+1];
        for(int i = 0 ; i <= n ; i++) graph[i] = new ArrayList<>();
        
        for(int[] road : roads){
            graph[road[0]].add(road[1]);
            graph[road[1]].add(road[0]);
        }
        
        cost = new int[n+1];
        Arrays.fill(cost,-1);
        
        bfs(destination);
        
        return Arrays.stream(sources)
            .map(idx->cost[idx])
            .toArray();
    }
    private void bfs(int start){
        Queue<Integer> q = new ArrayDeque<>();
        q.add(start);
        cost[start] = 0;
        
        while(!q.isEmpty()){
            
            int now = q.poll();
            int len = graph[now].size();
            
            for(int i = 0 ; i < len ; i++){
                int num = graph[now].get(i);
                if(cost[num] == -1){
                    q.add(num);
                    cost[num] = cost[now] + 1;
                }
            }
        }
    }
        
    
}

'Algorithm & Data Structures > Programers' 카테고리의 다른 글

Lv 3. [1차] 셔틀버스  (0) 2024.11.26
Lv 3. 가장 긴 펠린드롬  (3) 2024.11.21
Lv 3. 경주로 건설  (1) 2024.11.13
Lv 3. 디스크 컨트롤러  (1) 2024.11.11
Lv 3. 연속 펄스 부분 수열의 합  (0) 2024.11.07
'Algorithm & Data Structures/Programers' 카테고리의 다른 글
  • Lv 3. [1차] 셔틀버스
  • Lv 3. 가장 긴 펠린드롬
  • Lv 3. 경주로 건설
  • Lv 3. 디스크 컨트롤러
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (326)
      • Algorithm & Data Structures (246)
        • BOJ (104)
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (27)
        • SQL (21)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    스택
    백준
    Stack
    binarySearch
    PriorityQueue
    구현
    algorithm
    이분탐색
    동적계획법
    알고리즘
    프로그래머스
    SQL
    골드
    programmers
    유니온파인드
    baekjoon
    Union-Find
    Dijkstra
    dfs
    BFS
    dp
    DynamicProgramming
    투포인터
    Java
    다익스트라
    백트래킹
    경로압축
    후위순회
    전위순회
    unionfind
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
Lv 3. 부대복귀
상단으로

티스토리툴바