99클럽 코테 스터디 24일차 TIL + 가장 먼 노드 (java)

 

💡 문제

• 가장 먼 노드
• https://school.programmers.co.kr/learn/courses/30/lessons/49189#

권장 시간

• 1시간

소요 시간

• 1시간 30분 + a

 

나의 풀이 코드

import java.util.*;

public class Edge {
    int start;
    int end;
        
    public Edge(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;

        // 인접리스트 초기화
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }
        
        for (int[] e : edge) {
            list.get(e[0]).add(e[1]); // 간선의 시작 노드에서 끝 노드로 연결
            list.get(e[1]).add(e[0]); // 양방향 그래프이므로 반대 방향도 추가
        }
        
        Queue<Edge> q = new LinkedList<>();
        boolean[] isVisited = new boolean[n+1];
        int[] dist = new int[n+1]; // 1부터 각 노드까지의 최단 거리 저장

        q.add(new Edge(1, 1));
        isVisited[1] = true;
        
        while (!q.isEmpty()) {
            Edge curr = q.poll();

            // 현재 노드에 연결된 모든 이웃 노드 찾기
            for (int neighbor : list.get(curr.end)) {
                if (!isVisited[neighbor]) {
                    isVisited[neighbor] = true;
                    dist[neighbor] = dist[curr.end] + 1;
                    q.add(new Edge(curr.end, neighbor)); // 이웃 노드 큐에 추가
                }
            }
        }
        
        int maxVal = 0;
        for (int d : dist) {
            if (d > maxVal) {
                maxVal = d;
                answer = 1;
            } else if (d == maxVal) {
                answer++;
            }
        }
        
        return answer;
    }
}

 

주요사항

인접 리스트를 사용하는 방법에 대해 잘 알아야할 것 같다.

1 -> 2 3 
2 -> 1 3 
3 -> 1 2 

 

인접 리스트를 사용하면 해쉬맵처럼 key랑 values가 생기는 느낌?

그럼 해쉬맵을 사용했더라면 어땠을까? 궁금하네

 

그리고 “양방향” 그래프의 경우 두가지 경우를 모두 추가해야한다는 점도 유의하기!

 

사실 Edge 클래스없이 인접리스트에서 바로 get, add 하는 방법이 있는데 일단 내가 익숙한 대로 풀었다.

쓸데없이 클래스 하나 더 안쓰도록 노력하자!