99클럽 코테 스터디 24일자 TIL + 가장 먼 노드

이월(0216tw)·2024년 6월 12일

99클럽 TIL 개발자 취업 기능개발 미들러 이분탐색 자바 코딩테스트 코딩테스트준비 항해99

99클럽/알고리즘풀이

목록 보기

25/38

문제 출처

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days (leetcode)

학습 키워드

그래프

시도 방법

처음에는 BFS로 접근을 했는데 양방향 접근에 대해 잘 이해가 가지 않아
GPT에게 물어보고 이해를 할 수 있었다.

내가 작성한 코드

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.List;
import java.util.ArrayList;

class Solution {
public int solution(int n, int[][] edge) {

    List<List<Integer>> graph = new ArrayList<>(); 
    for(int i = 0 ; i < n+1 ; i++) {
        graph.add(new ArrayList<>()); //각 graph 요소는 List<Integer>             
    }
    
    
    
    //간선 정보를 인접 리스트에 추가
    //예
    //graph(0)
    //graph(1) -> [3, 2]
    //graph(2) -> [3, 1, 4, 5]
    //graph(3) -> [6, 4, 2, 1]
    //graph(4) -> [3, 2]
    //graph(5) -> [2]
    //graph(6) -> [3]        
    for(int[] edgeElement : edge) {
        graph.get(edgeElement[0]).add(edgeElement[1]); 
        graph.get(edgeElement[1]).add(edgeElement[0]); 
    }
    
    //BFS로 최단 경로 계산 
    int[] distance = new int[n+1]; 
    Arrays.fill(distance , -1); //distance배열은 원래 0인데 이를 모두 -1로 채움
    
    Queue<Integer> queue = new LinkedList<>(); 
    queue.add(1); //시작 노드 저장
    distance[1] = 0; //현재 distance 상태 [-1 , 0 , -1 , -1 , -1, -1 , -1]
    
    
    while(!queue.isEmpty()) {
        int currentNode = queue.poll(); 
        
        //만약 currentNode가 1이면 //graph(1) -> [3, 2] 가 출력이 된다. 
        for(int neighbor : graph.get(currentNode)) {
            
             if(distance[neighbor] == -1) { //아직 방문을 한 노드가 아니면
                 
                 //현재 위치 distance[currentNode] 를 기준으로 +1의 값을 넣어서
                 //주변 위치까지 필요한 거리를 갱신한다.
                 distance[neighbor] = distance[currentNode] + 1; 
                 queue.add(neighbor);
             }
        }
    
        //예) 
        /*
        
        currentNode : 1  , graph.get(1) => [3,2]
            
            distance[3] = 0+1 ; //아직 미방문이니까 
            큐에 3추가 
            distance[2] = 0+1 ; //아직 미방문이니까       
            큐에 2추가 
            
        currentNode : 3 , graph.get(3) => [6, 4, 2, 1]
            
            distance[6] = 1+1; //아직 미방문이고 현재 노드3 기준으로 1과의 거리가 1이었음
            큐에 6추가 
            distance[4] = 1+1; 
            큐에 4추가 
            distance[2] 는 1이므로 이미 방문한 상태이다. skip 
            distance[1] 는 0이므로 이미 방문한 상태이다. skip
            
        currentNode : 2 , graph.get(2) => [3, 1, 4, 5]
        
            distance[3] 은 1 이므로 이미 방문한 상태이다 skip 
            distance[1] 은 0 이므로 이미 방문한 상태이다 skip
            distance[4] 은 2 이므로 이미 방문한 상태이다 skip
            distance[5] = 1 + 1 ; //아직 미방문이고 현재 노드2 기준으로 1과의 거리가 1이었음
            큐에 5추가
        
        currentNode : 6 , graph.get(6) => [3] 
            
            distance[3] 은 이미 방문했다 skip 
        
        currentNode : 4 , graph.get(4) => [3, 2]
        
            distance[3] 은 이미방문했다 skip
            distance[2] 은 이미방문했다 skip
        
        currentNode : 5 , graph.get(2) => [2] 
        
            distance[2] 은 이미방문했다. skip
        
        더이상 큐에 내용이 없습니다.
        */
        
        // distance 현재 상태 : [-1 , 0 , 1 , 1 , 2 , 2 , 2]  
    }
    
    //가장 큰 distance 찾기             
    int max = 0 ; 
    for(int dis : distance) {
        if(max < dis) {
            max = dis ; 
        }
    }
                    
    //가장 큰 distance와 동일한 개수 카운드 
    int answer = 0 ; 
    for(int dis : distance) {
        if(max == dis) {
            answer+= 1; 
        }
    }
    
    return answer;
}

}