[Programmers] 가장 먼 노드

가장 먼 노드

그래프 문제입니다.
추가적으로 경로 탐색을 위해 BFS로 접근해야 하는 문제였습니다.

문제를 풀때 눈여겨 봐야할 조건이 딱히 있지 않은 문제였습니다.
다만 탐색을 할때 DFS가 아닌 BFS로 접근해야합니다.
저는 처음에 아무생각 없이 DFS로 접근했다가 연산양이 늘어나서 시간초과가 발생했습니다.
사실 문제를 처음에 잘 보셨다면 BFS로 풀어야 한다는 느낌이 들으실것 같습니다!

풀이 스타일

Java는 객체지향 언어이기 때문에 알고리즘 문제를 자바로 풀때 객체를 활용하는 방식으로 풀어야 하고,
이러한 방식은 복잡한 알고리즘 코드일 지라도 다른사람이 코드를 읽기 쉬워지게 만들어주는 것 같습니다.

Node 객체를 정의해놓고 간선이 존재하는 Node를 List<Node> linkedNodes 를 가지고 있도록 하였습니다.

또한 방문 한 노드는 Queue에 추가하지 않도록 하기위해 Node에 boolean타입의 visit 변수가 존재하고 있습니다.

일반적인 BFS 풀이방식으로 Queue를 사용하여 문제를 풀었습니다.

변수와 메소드 이름을 어느정도 신경써서 작성하였으니 천천히 코드를 읽어보시면 풀이를 이해하는데

큰 문제가 없을 것 같습니다.

코드

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

public class FarNode {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 6;
        int[][] edge = {{3, 6}, {4, 3}, {3, 2}, {1, 3}, {1, 2}, {2, 4}, {5, 2}};
        System.out.println(solution.solution(n, edge) == 3);
    }

}

class Solution {

    public int solution(int n, int[][] edge) {
        int answer = 0;
        List<Node> nodes = new ArrayList<>();
        makeNodes(n, nodes);

        addAllLinkedNode(edge, nodes);
        findFarDistance(nodes);

        int farDistance = nodes.stream()
                .map(Node::getDistance)
                .max(Integer::compareTo)
                .get();

        answer = (int) nodes.stream()
                .filter(node -> node.getDistance() == farDistance)
                .count();

        return answer;
    }

    private void findFarDistance(List<Node> nodes) {
        Node firstNode = findNode(1, nodes);
        firstNode.visit();

        List<Node> firstLinkedNodes = firstNode.getLinkedNode();

        for (Node node : firstLinkedNodes) {
            node.visit();
        }

        Queue<Node> nodeQueue = new LinkedList<>(firstLinkedNodes);

        while (!nodeQueue.isEmpty()) {
            Node nextNode = nodeQueue.poll();
            nextNode.visit();
            nextNode.addDistance();
            addNextLinkedNode(nodeQueue, nextNode);
        }
    }

    private void addNextLinkedNode(Queue<Node> nodeQueue, Node nextNode) {
        for (Node node : nextNode.getLinkedNode()) {
            if (node.isVisited()) {
                continue;
            }
            node.visit();
            node.changeBaseDistance(nextNode);
            nodeQueue.offer(node);
        }
    }

    private void addAllLinkedNode(int[][] edge, List<Node> nodes) {
        for (int[] link : edge) {
            int startIndex = link[0];
            int destIndex = link[1];
            Node startNode = findNode(startIndex, nodes);
            Node destNode = findNode(destIndex, nodes);
            linkNode(startNode, destNode);
        }
    }

    private void linkNode(Node startNode, Node destNode) {
        startNode.addLinkedNode(destNode);
        destNode.addLinkedNode(startNode);
    }

    private Node findNode(int nodeIndex, List<Node> nodes) {
        return nodes.stream()
                .filter(node -> node.getIndex() == nodeIndex)
                .findAny()
                .orElseThrow(RuntimeException::new);
    }

    private void makeNodes(int n, List<Node> nodes) {
        for (int i = 1; i <= n; i++) {
            nodes.add(new Node(i));
        }
    }

}

class Node {
    private Integer index;
    private boolean visited = false;
    private int distance = 0;
    private List<Node> linkedNode = new ArrayList<>();

    public Node(Integer index) {
        this.index = index;
    }

    public Integer getIndex() {
        return this.index;
    }

    public boolean isVisited() {
        return this.visited;
    }

    public List<Node> getLinkedNode() {
        return this.linkedNode;
    }

    public int getDistance() {
        return this.distance;
    }

    public void addDistance() {
        this.distance++;
    }

    public void changeBaseDistance(Node beforeNode) {
        this.distance = beforeNode.getDistance();
    }

    public void addLinkedNode(Node node) {
        this.linkedNode.add(node);
    }

    public void visit() {
        this.visited = true;
    }

}