kingsubin

import java.io.*;
import java.util.*;

public class Main {

    static int N, M, person1, person2, x, y;
    static LinkedList<Integer>[] nodeList;
    static boolean[] visited;
    static boolean check;

    static class Node {
        int index;
        int distance;

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }
    }

    public static void bfs(int start, int end) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(start, 0));

        while (!q.isEmpty()) {
            Node now = q.poll();

            if (visited[now.index]) return;
            visited[now.index] = true;

            if (now.index == end) {
                System.out.println(now.distance);
                check = true;
                return;
            }

            for (int next : nodeList[now.index]) {
                if (!visited[next]) {
                    q.offer(new Node(next, now.distance+1));
                }
            }

        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        person1 = Integer.parseInt(st.nextToken());
        person2 = Integer.parseInt(st.nextToken());

        nodeList = new LinkedList[N+1];
        visited = new boolean[N+1];

        for (int i = 0; i <= N; i++) {
            nodeList[i] = new LinkedList<Integer>();
        }

        M = Integer.parseInt(br.readLine());
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            x = Integer.parseInt(st.nextToken());
            y = Integer.parseInt(st.nextToken());

            nodeList[x].add(y);
            nodeList[y].add(x);
        }

        bfs(person1, person2);
        if (!check) {
            System.out.println(-1);
        }

    }
}

 

- 될거 같은데 계속 틀림 ....

- 다른 풀이 보고 다시 품 

- 혼자서 생각이 안난다 ....

 

0. bfs 생각

1. 연결관계 입력

2. bfs 수행 - Queue

2-1) 촌수를 계산할 변수가 필요해서 Node에 넣어서 사용

2-2) 큐에서 꺼낸 노드의 인덱스 값이 end와 같다면 distance 출력

2-3) 방문하지 않았을경우에만  꺼낸 노드의 인덱스와 연결된 노드들을 다시 큐에 추가 거리 +1 

 

 

---

www.acmicpc.net/problem/2644