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

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

프로그래머스

 

 

1. 문제 및 접근

 

n개의 노드가 있는 그래프 각 노드는 1번부터 번호대로

1번부터 가장 멀리 떨어 노드의 갯수를 구하라

이 말은 노드가 최단경로로 이동 했을 때 간선의 갯수가 가장 많은 노드

 

dfs로 구현하면 될 것 같은데 방문여부를 판단하고, 현재 노드에서 움직였는데

다시 돌아오는 노드가 있다면 ? check로 확인 ?

근데 다른 경로로 출발해도 만나게 되는 노드가 어디서 출발하냐에 따라 달라지는데 이걸 최단경로가 아니니

같거나 적은 것의 경로가 그 노드까지의 경로로 저장

이러면 중복이동이 좀 많을 것 같은데 더 효율적으로 움직일 순 없을까

 

전체탐색해야 하긴 하는데 현재 노드에서 얼마나 먼지 depth로 추가해야 하니 bfs로 구현해보자

 

 

제한사항

 

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

 

2. 그래프 만들기

 

들어온 배열을 그래프의 형태로 만들어줘야 한다.

그래프 만들 때 행렬을 써도 되지만

 

시간 복잡도의 차이는

•  인접행렬 : O(V^2)
• 인접 리스트 : O(V+E)

 

가변성 및 시간복잡도에 따라 선택하면 되는데 나는 리스트로 바꿔봤다.

 

 

(사실 도중에 추가될 일은 없긴 하지만.. 배열로 들어왔으니 한번 바꿔서 써보고 싶잖아 ?)

 

https://innovation123.tistory.com/110

 

 

 

 

https://jin1ib.tistory.com/entry/BFS-DFS-1

 

 

 

2-1. 인접리스트로 만들기

 

 

 

ArrayList타입을 받는 list 형태의 graph를 만들고,

 

노드의 갯수만큼 초기화시켜준다.

 

들어온 배열의 양방향 연관관계를 graph.get(index)로 서로 넣어주면 ?

 

 

 

index인 현재 node의 수가 어떤 수랑 연결되어 있는 지 알 수 있다.

 

 

1의 노드는  3, 2랑 이어져 있다.

2의 노드는 3, 1, 4, 5랑 이어져 있다.

~~

 

이런 식으로..

 

 

 

 

 

 

3. 풀이

 

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

    List<ArrayList<Integer>> graph = new ArrayList<>();

    for (int i = 0; i <=n; i++) {

        graph.add(new ArrayList<>());
    }

    for (int i = 0; i < edge.length; i++) {

        int u = edge[i][0];
        int v = edge[i][1];

        graph.get(u).add(v);
        graph.get(v).add(u);
    }




    int[] distance = new int[n+1]; // 1에서 얼마나 떨어져있는지 적어줘야함
    boolean[] visited = new boolean[n+1]; // 노드들이 방문한 적이 있는 지 확인

    Queue<Integer> queue = new LinkedList<>(); //bfs는 queue로
    queue.offer(1);
    visited[1] = true;


    while (!queue.isEmpty()) {
        int node = queue.poll(); // 꺼내온 queue 지금 값

        for (int now : graph.get(node)) { // 노드에 들어있는 수를 돌자
            if (!visited[now]) {
                visited[now] = true;
                distance[now] = distance[node] + 1; //현재 now의 수는 원래의 노드의 수와 +1만큼 떨어져있다
                //왜냐하면 현재 node에서 인접한 다음 노드들을 불러온 거라 +1해주면 됨 (1이 기준이니 계속 거리를 벌리기 위함)
                queue.offer(now);
            }
        }
    }

    int maxDist = 0;
    for (int i : distance) {

        if (maxDist < i) {
            maxDist = i;
        }

    }


    for (int i : distance) {
        if (maxDist == i) {
            answer++;
        }
    }

    return answer;

}

전체 풀이

 

 

 

 

 

3-1. BFS

 

 

bfs vs dfs는 이미 블로깅했으니 넘어가고,

 

 

 

먼저 bfs에서 방문 여부를 확인하기 위해 각 노드만큼의 visited 배열 선언,

 

 

 

그리고 우리가 궁금한 건 1의 노드에서 얼마나 떨어져 있냐?

 

 

를 저장하기 위해 각 노드 별로 1과의 얼만큼 떨어져 있는지를 적은 int 배열의 distance 선언!

 

 

 

3-2. while문

 

 

bfs는 순서대로 인접 노드를 방문해야 하니 queue로 구현

 

제일 시작 값인 queue에 1을 먼저 넣어주고,방문 표시를 해준다!

 

 

 

 

1.

while 문은 queue가 비어 있을 때 까지 반복하는데,

 

처음에 값을 꺼내 현재 node를 저장하고

 

graph의 node번째에 저장된 수들을 하나씩 돌면서 확인한다.

 

 

 

 

 

2.

꺼낸 노드가 방문하지 않았다면?

 

방문해줌과 동시에 방문표시해주고,

 

현재 방문한 그 node에 저장된 수가 (3)

 

ex) 1의 경우 [3,2]가 붙어(들어)있다.

 

 

 

 

 

3.

distance[3] 배열을 현재 1에서 불러왔으니 그 노드의 값에 +1 해줌!

다르게 말해 현재 3의 노드는 1과 하나의 distance를 가지고 있단 뜻!

1을 기준으로 현재 노드의 거리를 계산해서 넣어줘야하니까~

 

 

 

 

 

4.

그리고 현재 수를 offer로 queue에 넣어줌

 

queue = {3} ,{2} 

 

꺼내고 넣고 계속 반복이다~

 

 

 

 

중요한 점은 방문했거나, 같은 수 (이것도 방문했던거)는 넣지 않음

 

 

 

현재 거리를 찍어보면

 

1번과의 인덱스 별 거리를 알 수 있다.

 

 

1번은 자기 자신과의 거리는 "0"

2번은 하나의 distance를 갖고

3번도 마찬가지

~~

 

 

 

3-3. 정답 확인

 

 

 

distance에 저장된 각 노드들 중에서 가장 큰 값을 가지는 거리를 찾는다.

 

현재의 경우 1이랑 가장 멀리 떨어져 있는 distance는 2의 거리만큼 떨어져 있다.

 

maxDist = 2

 

(4, 5, 6의 노드가 해당함)

 

 

 

 

 maxDist와 같은 거리를 가진 애를 세어주고,

 

 

 

반환!

 

 

 

 

 

 

4.  마무리

 

 

그래프의 인접행렬을 구현하는 방법을 찾다가 양방향 단반향 여러 그래프를 구현할 수 있어야겠다고 생각이 들었다..

 

부족한 것은 많고 이런 게 바로 바로 떠올라서 해결할 수 있는 날이 올까..

 

 

distance를 어떻게 구현할지 고민을 많이 했다.

 

bfs로 탐색은 하겠는데 1과의 거리를 어떤 형식으로 넣어줄까 ?에서 바로 떠오르지 않아서..

 

 

 

 

요새 재밌는 것들이 너무 많다 사실 나는 코딩과 수학적 사고가 취향에 맞긴 하지만,

따지고 보면 모든 게 궁금하다

세상이 돌아가는 이치와 원리 등..

 

궁금한 것들이 많아서 관련 공부만 죽어라 해도 모자른데.. 물리에 빠져 버렸다 ㅠㅠ

 

왜 이렇게 한량같나 싶다.. 뇌과학 그만보고 코딩 책 더 빌려라~