프로그래머스 | 가장 먼 노드 - java

프로그래머스

 

# 핵심

인접 리스트를 사용해서 그래프 구현 이후 BFS 탐색

(가장 멀리 떨어진 노드를 구한다는 것은 즉 최단 거리가 가장 먼 노드를 구한다는 것! 최단거리 탐색 = BFS !!)

 

# 실패 코드 (인접 행렬을 이용한 그래프 구현)

import java.util.*;

class Solution {

    boolean[] visited;
    int[] dist;

    public int solution(int n, int[][] edges) {
        int[][] map = new int[n][n];
        visited = new boolean[n];
        dist = new int[n];

        Arrays.fill(dist, Integer.MAX_VALUE);

        for (int[] edge : edges) {
            // 양방향 연결
            map[edge[0] - 1][edge[1] - 1] = 1;
            map[edge[1] - 1][edge[0] - 1] = 1;
        }

        bfs(map, 0);

        Arrays.sort(dist);
        int cnt = 1;
        for(int i = dist.length - 1; i > 0; i--, cnt++) {
            if(dist[i] != dist[i - 1]) break;
        }
        return cnt;
    }

    private void bfs(int[][] map, int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        dist[v] = 0;

        while(!queue.isEmpty()) {
            Integer w = queue.poll();
            for(int i = 0; i < map[w].length; i++) {
                if(map[w][i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                    dist[i] = Math.min(dist[i], dist[w] + 1);
                }
            }
        }
    }
}

- 마지막 두개의 테스트 케이스에서 메모리 초과가 발생했다.

노드의 개수가 2만개 이므로 인접행렬을 만들게 된다면 2만 * 2만 * 4(int)의 메모리 공간을 사용하게 되는데, 그래도 충분히 통과가 가능하지 않을까? 싶었는데 안타깝게도 그렇지 않았다.

 

그래서 인접 행렬 대신 인접 리스트를 사용해서 그래프를 구현해보도록 수정해보았다.

 

(+) 다른 블로그 글들 보니까 int[][] 배열이 아니라 boolean[][] 배열 사용하면 인접 행렬로도 통과 된다고 한다.

 

 

# 통과 코드 (인접 리스트를 통한 그래프 구현)

import java.util.*;

class Solution {

    List<List<Integer>> adjList = new ArrayList<>(); // 인접 리스트
    boolean[] visited; // 해당 노드를 방문했는지?
    int[] dist; // 노드별 최단 거리 저장

    public int solution(int n, int[][] edges) {
        visited = new boolean[n];
        dist = new int[n];
		
        // MAX_VALUE 값으로 최단거리 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);

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

        for (int[] edge : edges) {
            // 양방향 연결
            adjList.get(edge[0] - 1).add(edge[1] - 1);
            adjList.get(edge[1] - 1).add(edge[0] - 1);
        }

        bfs(0);

        Arrays.sort(dist); // 최단거리 오름차순 정렬
        int cnt = 1;
        for(int i = dist.length - 1; i > 0; i--, cnt++) {
            if(dist[i] != dist[i - 1]) break; // 최댓값 같은게 몇개 있는지 카운트
        }
        return cnt;
    }

    private void bfs(int v) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(v);
        visited[v] = true;
        dist[v] = 0;

        while(!queue.isEmpty()) {
            Integer w = queue.poll();
            for (Integer e : adjList.get(w)) {
                if(!visited[e]) {
                    queue.add(e);
                    visited[e] = true;
                    dist[e] = Math.min(dist[e], dist[w] + 1);
                }
            }
        }
    }
}

다행히도 인접 행렬의 문제가 맞았다!

인접 리스트로 그래프 구현 방식을 변경하고 나니 모든 테스트 케이스를 무사히 통과할 수 있었다.

 

 

이번 문제는 3렙이지만 생각보다 쉽게 풀었다! ㅎㅎ

 

# 느낀점

1. 최단거리 탐색은 BFS

2. 문제를 풀면서 느낀건데 ArrayList와 LinkedList의 차이가 뭘까? 평소에 별 생각없이 사용해왔던 것 같다. 한번 찾아볼것