프로그래머스 코딩테스트 연습 - 가장 먼 노드 (다익스트라, 플로이드-와샬, DFS)

# 주소

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

프로그래머스

# 문제

문제 설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예nvertexreturn

6

[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

# 문제 해설 및 코드 리뷰

 

* 기존 코드 *

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int[][] arr = new int[n + 1][n + 1];
        for (int i = 0; i <= n; i++){
            Arrays.fill(arr[i], 20000);
            arr[i][i] = 0;
        }
        for(int i = 0; i < edge.length; i++){
            int a = edge[i][0];
            int b = edge[i][1];
            arr[a][b] = arr[b][a] = 1;
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                for(int k = 1; k <= n; k++){
                    arr[j][k] = Math.min(arr[j][k], arr[j][i] + arr[i][k]);
                }
            }
        }
        int answer = -1;
        int count = 0;
        for(int i = 2; i <= n; i++){
            if(answer < arr[1][i]){
                count = 0;
                answer = arr[1][i];
            }else if(answer == arr[1][i]){
                count++;
            }
        }
        return count + 1;
    }
}

이 문제를 플로이드-와샬 문제로 접근하면 틀리게 됩니다.

1 ~ 7번 테스트 케이스는 모두 정답이라고 뜨는데 8 ~ 10번 테스트 케이스는 시간초과가 다른 풀이를 찾아야 했습니다.

그렇기에 

class Solution{
    static boolean[][] visit;
    static boolean[] check;
    static Queue<Integer> queue = new LinkedList<>();
    public int solution(int n, int[][] edge){
        int answer = 0;

        visit = new boolean[n + 1][n + 1];
        check = new boolean[n + 1];
        for(int i = 0; i < edge.length; i++){
            visit[edge[i][0]][edge[i][1]] = true;
            visit[edge[i][1]][edge[i][0]] = true;
        }
        queue.offer(1);
        check[1] = true;
        answer = dfs(n);
        return answer;
    }
    static int dfs(int n){
        int count = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                int now = queue.poll();
                for(int j = 1; j <= n; j++){
                    if(visit[j][now] && !check[j]){
                        check[j] = true;
                        queue.offer(j);
                    }
                }
            }
            count = size;
        }
        return count;
    }
}

DFS 방법으로 한 번 풀이를 살펴보겠습니다.

풀이를 하기 전, 어떻게 접근했는지 정리하겠습니다.

1. 2차원 배열의 boolean타입(int도 가능)과 1차원의 boolean[]타입으로 인덱스 체크

2. Queue를 이용하여 사이즈 갱신

3. 간선간의 값은 모두 1이므로 true, false로 조절하고 매번 queue의 크기를 갱신 반복

직접 코드를 보며 살펴보겠습니다.

int answer = 0;

visit = new boolean[n + 1][n + 1];
check = new boolean[n + 1];

visit은 2차원, check는 1차원으로 각각 n + 1크기의 크기로 선언합니다.

이유는 이 배열에 들어갈 데이터들은 1 ~ n 까지이기 때문입니다.

이후

for(int i = 0; i < edge.length; i++){
    visit[edge[i][0]][edge[i][1]] = true;
    visit[edge[i][1]][edge[i][0]] = true;
}

for문을 이용하여 visit[첫번째][두번째] = visit[두번째][첫번째] = true로 초기화합니다.

queue.offer(1);
check[1] = true;
answer = dfs(n);

queue에 1을 넣고 check[1] = true를 넣어줍니다.

queue에 1을 넣는 이유는 1에서 부터 시작할 것이기 때문에 먼저 할당을 해주는 것이며 재방문을 피하기 위해 check[1] = true가 되어야 합니다.

dfs는 어떻게 생겼는지 살펴보겠습니다.

static int dfs(int n){
    int count = 0;
    while(!queue.isEmpty()){
        int size = queue.size();
        for(int i = 0; i < size; i++){
            int now = queue.poll();
            for(int j = 1; j <= n; j++){
                if(visit[j][now] && !check[j]){
                    check[j] = true;
                    queue.offer(j);
                }
            }
        }
        count = size;
    }
    return count;
}

이렇게 생겼습니다. 간단하죠?

count = 0으로 일단 두겠습니다.

이 count는 queue의 크기를 받아올 것인데 나중에 다시 보겠습니다.

while(!queue.isEmpty()){
    int size = queue.size();
    for(int i = 0; i < size; i++){
        int now = queue.poll();

while문을 이용하여 queue가 비는 것을 방지하고, size에는 queue의 size를 받아옵니다.

이후 size크기 동안 queue의 첫 번째 요소를 now로 받아올텐데요.

최초에 1을 담았으니 1을 담습니다.

for(int j = 1; j <= n; j++){
    if(visit[j][now] && !check[j]){
        check[j] = true;
        queue.offer(j);
    }
}

그러고 나면 다시 for문을 이용하여 1 부터 n까지 탐색을 할 것입니다.

만약 visit[j][now]가, 그러니까 queue에서 담아온 1고 연결된 visit[i]들 중에서 !check[j]인 것.

방문하지 않은 j요소를 찾습니다. 

이 때에는 n번의 시간 복잡도를 가지게 됩니다.

만약 방문하지 않았고 1과 연결되어 있다면 1고 이웃한 인덱스 이므로 해당 인덱스를 true로 바꾸고

queue에 삽입합니다.

만약 1과 연결된 인덱스가 2개 있었다면 queue에는 총 2개가 담기게 되고 for문을 마치고 빠져나옵니다.

이후 count = size로 갱신합니다.

    }
        count = size;
    }
    return count;
}

생각해보면 간단한데, 가장 멀리 있는 인덱스라면 당연히 count가 새로 갱신되고 갱신되어 마지막에 갱신되는 인덱스의 거리일 때 count가 가장 먼 노드와의 거리일 것입니다.

따라서 size라는 queue의 크기를 앞전에 선언했던 것은 for문을 돌리기 위해서 인 것도 있지만 이 size를 count에 다시 갱신하여 return하여 정답을 출력하면 인정이 되는 것을 확인할 수 있습니다.

 

플로이드-와샬을 지난 시간에 써봤어서 한 번 더 활용해보려 했는데 시간 초과가 나네요..

다익스트라로는 아직 시도를 안해봤는데 해보고 만약 정답이 되면 여기에 추가 코드로 남기겠습니다.

감사합니다.