백준 2644: 촌수계산[JAVA]

https://www.acmicpc.net/problem/2644

 

[난이도]

- Silver 2

 

[알고리즘]

- bfs

 

[코드]

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

public class Main {
    static ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
    static int[] dist;
    static boolean[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int n = Integer.parseInt(st.nextToken());
        dist = new int[n + 1];
        visited = new boolean[n + 1];

        st = new StringTokenizer(br.readLine(), " ");
        int p1 = Integer.parseInt(st.nextToken());
        int p2 = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph.get(x).add(y);
            graph.get(y).add(x);
        }
        System.out.println(bfs(p1, p2));
    }

    static int bfs(int start, int end) {
        Queue<Integer> queue = new LinkedList<>();
        dist[start] = 0;
        visited[start] = true;
        queue.offer(start);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            for (int i = 0; i < graph.get(cur).size(); i++) {
                if (!visited[graph.get(cur).get(i)]) {
                    dist[graph.get(cur).get(i)] = dist[cur] + 1;
                    if (graph.get(cur).get(i) == end) {
                        return dist[graph.get(cur).get(i)];
                    }
                    queue.offer(graph.get(cur).get(i));
                    visited[graph.get(cur).get(i)] = true;
                }
            }
        }
        return -1;
    }
}

 

[풀이]

ArrayList<ArrayList<Integer>>를 활용해 가변적 배열처럼 사용한다. 

dist 배열은 p1기준으로 봤을때 각 사람의 촌수를 저장한다.

visited 배열은 이미 촌수를 계산했다면 다시 계산되면 안되기때문에 계산했는지 안했는지 체크하는 배열이다.

큐에 담긴 숫자를 꺼내 해당숫자와 연관이 있으면서 촌수를 계산하지 않은 숫자라면 큐에 꺼낸 숫자의 촌수 + 1을 연관되어있는 숫자에 기록해준다.