[코딩테스트] 가장 먼 노드

문제

---

가장 먼 노드 문제 바로가기

제출 코드(JAVA)

---

첫번째 코드 제출

   public int solution(int n, int[][] edge) {
        int result = 0;
        boolean[][] maps = new boolean[n+1][n+1];
        int[] distance = new int[n+1];

        Arrays.stream(edge)
                .forEach(v -> {
                    maps[v[1]][v[0]] = maps[v[0]][v[1]] = true;
                });

        Queue<Integer> nodes = new LinkedList<Integer>();
        nodes.add(1);

        int maxDist = 0;
        while(!nodes.isEmpty()) {
            int i = nodes.poll();

            for (int j = 2; j <= n; j++) {
                if( distance[j] == 0 && maps[i][j] ) {
                    distance[j] = distance[i] + 1;
                    nodes.add(j);
                    maxDist = Math.max(maxDist,distance[j]);
                    maps[i][j] = maps[j][i] = false;
                }
            }
        }

        for (int d : distance) {
            if( maxDist == d )
                result ++;
        }

        return result;
    }

1) 경로 유무 확인할 maps 생성
2) BFS로 각 탐색 후, 최단거리 업데이트 진행

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.74ms, 52.5MB)
테스트 2 〉	통과 (0.79ms, 52.2MB)
테스트 3 〉	통과 (0.87ms, 53.8MB)
테스트 4 〉	통과 (1.06ms, 52.9MB)
테스트 5 〉	통과 (8.82ms, 53MB)
테스트 6 〉	통과 (18.05ms, 58.7MB)
테스트 7 〉	통과 (629.85ms, 250MB)
테스트 8 〉	통과 (1898.09ms, 551MB)
테스트 9 〉	통과 (1267.21ms, 552MB)

두번째 코드 제출

  import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<Integer>[] path = new ArrayList[n];
        ArrayList<Integer> bfs = new ArrayList<Integer>();
        int answer = 0;
        int[] dist = new int[n];
        dist[0] = 1;
        int max = 0;

        for(int i = 0; i < edge.length; i++) {
            int num1 = edge[i][0] - 1;
            int num2 = edge[i][1] - 1;
            if(path[num1] == null)
                path[num1] = new ArrayList<Integer>();
            if(path[num2] == null)
                path[num2] = new ArrayList<Integer>();
            path[num1].add(num2);
            path[num2].add(num1);
        }

        bfs.add(0);
        while(!bfs.isEmpty()) {
            int idx = bfs.get(0);
            bfs.remove(0);
            while(!path[idx].isEmpty()) {
                int num = path[idx].get(0);
                path[idx].remove(0);
                bfs.add(num);
                if(dist[num] == 0) {
                    dist[num] = dist[idx] + 1;
                    max = dist[num];
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(dist[i] == max)
                answer++;
        }

        return answer;
    }
}

탐색할 경로만 저장 후 진행해 효율성이 올랐다

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.11ms, 52.5MB)
테스트 2 〉	통과 (0.16ms, 52.4MB)
테스트 3 〉	통과 (0.39ms, 52.5MB)
테스트 4 〉	통과 (2.37ms, 54MB)
테스트 5 〉	통과 (6.64ms, 54.2MB)
테스트 6 〉	통과 (18.12ms, 59.3MB)
테스트 7 〉	통과 (178.30ms, 74.7MB)
테스트 8 〉	통과 (72.72ms, 76.6MB)
테스트 9 〉	통과 (338.69ms, 74.6MB)

제출 코드(Python)

---

코드 제출

def solution(n, edge):
    graph =[  [] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.03ms, 10.3MB)
테스트 4 〉	통과 (0.36ms, 10.3MB)
테스트 5 〉	통과 (1.26ms, 10.5MB)
테스트 6 〉	통과 (2.71ms, 11.2MB)
테스트 7 〉	통과 (28.68ms, 19MB)
테스트 8 〉	통과 (36.62ms, 23.8MB)
테스트 9 〉	통과 (57.17ms, 23.3MB)