최단거리

최단거리

 

문제

---

그래프와 출발점, 도착점이 주어질 때 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 예를 들어, 아래 그림에서 출발 정점이 0, 도착 정점이 10이라고 할 때, 최단거리는 3이다.

 

입력

---

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. ( 1 ≤ N ≤ 10,000, 1 ≤ M ≤ 1,000,000 ) 둘째 줄부터 간선의 정보가 주어진다. 각 줄은 두 개의 숫자 a, b로 이루어져 있으며, 이는 정점 a와 정점 b가 연결되어 있다는 의미이다. M+1 번째 줄에 대하여 출발점과 도착점의 정점 번호가 주어진다.

 

출력

---

출발점에서 도착점까지 이동하기 위한 최단거리를 출력한다.

 

예제 입력

11 14
0 1
0 2
1 2
1 4
1 5
2 3
3 7
4 7
4 9
4 10
5 6
6 8
6 10
7 8
0 10

예제 출력

3

코드 /bfs

//최단거리

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

public class Main {

    public static ArrayList<Node> box = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c = 0;
        int d = 0;
        int result = 0;

        a = sc.nextInt();

        for (int i = 0; i < a; i++) {
            Node node = new Node(i);
            box.add(node);
        }

        b = sc.nextInt();

        for (int i = 0; i < b; i++) {
            c = sc.nextInt();
            d = sc.nextInt();
            box.get(c).getNodes().add(box.get(d));
            box.get(d).getNodes().add(box.get(c));
        }

        int start = sc.nextInt();
        int goal = sc.nextInt();

        Queue<Node> queue = new LinkedList<>();

        Node st = box.get(start);
        queue.offer(st);
        st.setHeight(0);
        st.setChecked(true);

        bigWhile:
        while (!queue.isEmpty()) {

            Node node = queue.poll();

            for (int i = 0; i < node.getNodes().size(); i++) {

                Node offer = node.getNodes().get(i);

                if (offer.getData() == goal) {
                    result = offer.getHeight();
                    break bigWhile;
                }

                if (!offer.isChecked()) {
                    offer.setHeight(node.getHeight() + 1);

                    queue.offer(offer);
                    offer.setChecked(true);
                }

            }

        }

        System.out.println(result);

    }


}


class Node {

    private boolean isChecked;
    private int data;
    private int height;
    private ArrayList<Node> nodes;

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public boolean isChecked() {
        return isChecked;
    }

    public void setChecked(boolean checked) {
        isChecked = checked;
    }

    public Node(int data) {
        this.setChecked(false);
        this.data = data;
        nodes = new ArrayList<>();
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public ArrayList<Node> getNodes() {
        return nodes;
    }

    public void setNodes(ArrayList<Node> nodes) {
        this.nodes = nodes;
    }
}