[Algorithm] 너비 우선 탐색(Breath First Search)

설명

• 그래프에서 데이터 탐색할 경우 너비를 우선으로 탐색하는 방식
• 거리가 가까운 곳부터 방문하는 방식으로 최단 거리 탐색시에도 사용
• 큐를 사용
• 참고
  • https://youtu.be/66ZKz-FktXo

참고 그래프

• BFS
  • 1 2 3 4 5 6 7

 

Node 코드

public class Node<T> {
    private T value;
    private boolean isVisited;
    private List<Node<T>> nearNodes = new ArrayList<>();

    public Node(T value) {
        this.value = value;
    }

    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    public boolean isVisited() {
        return isVisited;
    }

    public void setVisited(boolean visited) {
        isVisited = visited;
    }

    public List<Node<T>> getNearNodes() {
        return nearNodes;
    }

    public void setNearNodes(List<Node<T>> nearNodes) {
        this.nearNodes = nearNodes;
    }
}

Graph 코드

public class Graph<T> {
    private Map<T, Node<T>> graph = new HashMap<>();

    public Graph(T[][] graph) {
        for (T[] values : graph) {
            join(values[0], values[1]);
        }
    }

    public Node<T> getNode(T value) {
        return graph.get(value);
    }

    private void join(T value1, T value2) {
        Node<T> node1 = graph.getOrDefault(value1, new Node<T>(value1));
        Node<T> node2 = graph.getOrDefault(value2, new Node<T>(value2));

        node1.getNearNodes().add(node2);
        node2.getNearNodes().add(node1);

        graph.put(value1, node1);
        graph.put(value2, node2);
    }
}

Graph<Integer> graph = new Graph<>(new Integer[][] {
    new Integer[] {1, 2},
    new Integer[] {1, 3},
    new Integer[] {2, 3},
    new Integer[] {2, 4},
    new Integer[] {2, 5},
    new Integer[] {3, 6},
    new Integer[] {3, 7},
    new Integer[] {4, 5},
    new Integer[] {6, 7},
});

BFS 코드

public class Solution {
    public static <T> List<T> search(Graph<T> graph, T start) {
        Queue<Node<T>> queue = new LinkedList<>();
        List<T> result = new ArrayList<>();

        // 시작 노드를 방문했다고 표시하고 큐에 추가
        Node<T> startNode = graph.getNode(start);
        startNode.setVisited(true);
        queue.add(startNode);

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            Node<T> node = queue.remove();
            result.add(node.getValue());

            // 인접 노드 중 방문하지 않은 노드를 방문했다고 표시하고 큐에 추가
            for (Node<T> nearNode : node.getNearNodes()) {
                if (!nearNode.isVisited()) {
                    nearNode.setVisited(true);
                    queue.add(nearNode);
                }
            }
        }

        return result;
    }
}

class SolutionTest extends Specification {
    @Unroll
    def "#graph, #start -> #result"() {
        expect:
        Solution.search(new Graph<Integer>(graph as Integer[][]), start as Integer) == result as List<Integer>

        where:
        graph                                                                    | start | result
        [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 5], [6, 7]] | 1     | [1, 2, 3, 4, 5, 6, 7]
        [[1, 2], [1, 3], [2, 3], [2, 4], [2, 5], [3, 6], [3, 7], [4, 5], [6, 7]] | 2     | [2, 1, 3, 4, 5, 6, 7]
    }
}