프로그래머스_가장 먼 노드_Java (Graph, BFS)

문제 풀이에 대한 오류 지적 및 개선 방향 제시는 항상 환영합니다.
알고리즘 문제를 엄청 잘 풀고 막 문제 보자마자 아 이거네 쉽네 ㅎㅎ 이렇게 푸는 입장이 아니라서
그 어떤 문제에 대한 비판 지적 방향 제시는 언제나 감사하게 받겠습니다. 

이 문제가 올라가는 저장소 : https://github.com/hwk0911/junit-tdd 

hwk0911/Junit-TDD

문제 설명

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

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

제한사항

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

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

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

해설

문제를 해결하기 위해서는 당연히 그래프를 그릴 수 있어야 하며, 해당 문제를 읽고
이 문제에 적합한 탐색방법을 찾을 수 있어야 수월하게 풀 수 있다.

우리가 기본적으로 그래프에 관련된 문제가 나왔을 때, 주로 DFS와 BFS를 떠올릴 것이다.

DFS의 경우, 깊이 우선 탐색으로, 말 그대로 우선 최대한 깊게 내려가는 것을 목표로 하는
탐색 방법이다. 주로 미로를 탐색하거나, 모든 노드를 방문하고자 할 때 사용한다.

BFS의 경우, 너비 우선 탐색으로, 말 그대로 깊이가 아닌, 너비를 우선으로 탐색하는 방법이다.
쉽게 말해, 한층 한층 검사를 한다 생각하면 쉽다. 주로 두 노드의 최단 혹은 임의의 경로를 찾을 때
사용한다.

아직 어떤 것이 더 효율적인지 감이 잡히지 않았다면, 문제를 살펴보자.

문제의 조건

1. 각 노드는 1부터 n까지 번호가 적혀있다.
2. 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하려 한다.
3. 가장 멀리 떨어진 노드는 최단경로로 이동했을 때, 간선의 개수가 가장 많은 노드이다.
4. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어진다.
5. 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성하라.

제한 사항

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

이 문제의 핵심 요구사항은, 1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 것이다.

특정 노드에서 가장 멀리 떨어져 있다 => 최단 경로에서 간선의 개수가 가장 많은 노드로 볼 수 있다.
여기서 DFS를 사용하지 못하는 가장 중요한 조건이 나온다. 최단 경로.

DFS의 경우, 탐색 후 나온 결괏값이 항상 최적의 결괏값이라 볼 수 없다.
따라서 최단 경로를 구하는데 적합하지 못하다. 또한, 모든 노드를 하나하나 탐색해야 하므로,
시간이 상당히 오래 걸린다.

BFS의 경우 위에서 간단하게 한층 한층 탐색하는 방법이라 서술했다.
즉 최단경로를 구하기에 적합하다.

설명을 돕기 위해, 위의 그래프를 다른 각도로 보겠다.

위의 그래프를 살펴보면, 당연히 1에서 가장 먼 노드는 4, 5, 6 노드 3개이다.

1층부터 3층까지 있는 건물에서, 1층을 기준으로 가장 먼 층수는 3층이 되는 것 과 마찬가지다.

따라서 BFS를 사용하여 문제를 해결한다.

Solution.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Programmers_Graph_가장먼노드 {
    static boolean[] visited;

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

        this.visited = new boolean[n];
        List<List<Integer>> nodeList = setList(n, edge);
        Queue<Integer> nodeQue = new LinkedList<>();
        nodeQue.offer(0);
        this.visited[0] = true;

        while(!nodeQue.isEmpty()) {
            answer = nodeQue.size();
            nodeQue = setQue(nodeQue, nodeList);
        }

        return answer;
    }

    public List<List<Integer>> setList (int n, int[][] edge) {
        List<List<Integer>> nodeList = new ArrayList<>();
        List<Integer> temp;

        for(int index = 0, size = n ; index < size ; ++index) {
            nodeList.add(new ArrayList<>());
        }

        for(int index = 0, size = edge.length ; index < size ; ++index) {
            int start = edge[index][0] - 1;
            int end = edge[index][1] - 1;

            temp = nodeList.get(start);

            if(!temp.contains(end)) {
                temp.add(end);
            }

            temp = nodeList.get(end);

            if(!temp.contains(start)) {
                temp.add(start);
            }
        }

        return nodeList;
    }

    public Queue<Integer> setQue (Queue<Integer> queue, List<List<Integer>> nodeList) {
        List<Integer> temp;
        Queue<Integer> newQueue = new LinkedList<>();

        while(!queue.isEmpty()) {
            temp = nodeList.get(queue.poll());

            for(int index = 0, size = temp.size() ; index < size ; ++index) {
                int nodeLink = temp.get(index);

                if(!this.visited[nodeLink]) {
                    newQueue.offer(nodeLink);
                    this.visited[nodeLink] = !this.visited[nodeLink];
                }
            }
        }

        return newQueue;
    }
}

전역으로 선언된 boolean [] visited

각 노드들에 대해 방문 여부를 판단한다.
각 노드의 번호를 인덱스로 false면 미방문, true면 방문한 것으로 판단한다.

public int solution

1. this.visited = new boolean [n];
   1. 노드의 개수는 n이므로, n만큼의 boolean배열로 할당한다.
2. List <List <Integer>> nodeList = setList(n, edge);
   1. 이중 List구조를 이용하여, 겉의 List는 각 노드의 번호를 의미하며,
      내부의 List는 각 노드마다 연결된 다른 노드들을 의미한다.
3. Queue <Integer> nodeQue = new LinkedList <>();
   1. 기본적으로 BFS는 큐의 구조를 갖는다.
   2. 따라서 Queue를 통하여 BFS구현의 편의성을 챙겼다.
4. nodeQue.offer(0);
   
   1. 탐색의 시작 위치를 1로 고정하였기 때문에, 0을 추가해준다.
   2. 1이 아닌 0인 이유는, setList() 메서드에서 마저 서술하겠다.
5. this.visited [0] = true;
   1. 시작 노드를 Queue에 넣었으므로, visited의 0번째 원소를 방문한 것으로 초기화한다.
6. while(! nodeQue.isEmpty()) {
   1. 반복문을 통해, nodeQue가 비어있는 상태를 체크한다.
   2. 가장 먼 노드들의 모임일 경우, 다음 노드의 정보가 존재하지 않는다.
   3. 따라서 nodeQue는 비어있는 상태가 된다. 이때 반복문을 탈출하기 위해 설정했다.
7. answer = nodeQue.size();
   1. 노드의 개수를 반환하는 것이 문제의 요구사항이므로, 사이즈만 체크하여 개수를 저장한다.
8. nodeQue = setQue(nodeQue, nodeList);
   1. nodeQue에 저장된, 현재 층의 노드들에 각 각 연결된 다음 층의 노드들을 
      새로운 Queue에 저장하여, nodeQue를 이것으로 초기화한다.
9. } 
   1. 7 ~ 8번 반복 (! nodeQue.isEmpty() )
10. answer를 반환하고, 함수를 종료.

public List <List <Integer>> setList (int n, int [][] edge)

각 노드들에 대한 연결된 노드를 확인하기 위해, 직접적인 그래프를 구현하기보다
List를 통해 간이 그래프를 구성하기 위한 메서드다.

1. List <List <Integer>> nodeList = new ArrayList <>();
   1. 새로운 ArrayList 생성, 노드에 대한 인덱스를 갖게 된다.
2. List <Integer> temp
   1. 바깥 List의 내부 List를 동적으로 적용하기 위한 List를 선언한다.
3. for (int index = 0, size = n, index < size ; ++index) { }
   1. 노드의 수만큼 반복한다.
4. nodeList.add(new ArrayList <>());
   1. 노드의 수만큼 바깥 List를 확장한다.
5. 4번 반복 ( index < n )
6. for (int index = 0, size = edge.length ; index < size ; ++index) { }
   1. 주어진 간선의 수만큼 반복한다.
7. int start = edge [index][0];
   
   1. 첫 숫자를 쉽게 불러오기 위해 start변수를 선언 및 초기화
8. int end = edge [index][1];
   1. 두 번째 숫자를 쉽게 불러오기 위해 end변수를 선언 및 초기화
9. temp = nodeList.get(start);
   1. 첫 번째 숫자를 인덱스로, 원소 List를 불러 temp를 초기화한다.
10. if(! temp.contains(end) )
    1. 해당 리스트에 end를 원소로 포함하는지 판단. 포함되었다면 중복이므로 추가하지 않음.
11. temp.add(end) 
    1. 해당 리스트에 중복이 아닌 end 원소를 추가
12. 양방향 이므로, 9 ~ 10번 start와 end를 서로 바꾸어 실행한다.
13. 7 ~ 12번 반복 (edge의 배열 길이만큼)

public Queue <Integer> setQue (Queue <Integer> queue, List <List <Integer>> nodeList)

1. List <Integer> temp
   1. nodeList의 원소를 저장하기 위한 List 선언
2. Queue <Integer> newQueue = new LinkedList <>();
   1. 반환될 새로운 Queue를 선언한다.
3. while(! queue.isEmpty()) { }
   1. queue가 비어있지 않다면, 반복한다.
4. temp = nodeList.get(queue.poll())
   1. queue의 첫 번째 원소를 출력하여 인덱스로 활용한다.
   2. nodeList의 인덱스에 해당하는 List를 반환하여 temp를 초기화한다.
5. for (int index = 0, size = temp.size () ; index < size ; ++index) { }
   1. temp의 사이즈만큼 반복한다.
6. int nodeLink = temp.get(index);
   1. temp에 저장된 index에 해당하는 원소를 쉽게 부르기 위해 nodeLink변수를 선언
7. if (! this.visited [nodeLink]) {
   1. nodeLink에 해당되는 노드가 방문된 적 있는지 판단한다.
   2. 방문한 적 없다면, enwQueue에 저장한다.
   3. 해당 노드는 이제 방문한 것이 되므로, this.visited [index] =! this.visited [index];로 true로 만든다.
8. 6 ~ 7 반복 (각 temp별 사이즈만큼)
9. 4 ~ 8 반복 (queue가 비어있지 않을 때)
10. newQueue를 반환한다.

 

SolutionTest

import org.junit.jupiter.api.Test;

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

class Programmers_Graph_가장먼노드Test {

    Programmers_Graph_가장먼노드 main = new Programmers_Graph_가장먼노드();

    @Test
    void solution() {
        int n = 6;
        int[][] vertex = {{3, 6}, {4, 3},{3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};

        assertThat(3, is(main.solution(n, vertex)));

        n = 4;
        int[][] vertex_2 = {{1,2}, {1,3}, {3,4}, {4,2}};
        assertThat(1, is(main.solution(n, vertex_2)));

        n = 4;
        int[][] vertex_3 = {{1,2}, {1,3},
                {2,3}, {2,4},
                {3,4}};
        assertThat(1, is(main.solution(n, vertex_3)));
    }
}