[백준/JAVA] 2644번: 촌수계산

코테/백준

[백준/JAVA] 2644번: 촌수계산

imname1am 2023. 7. 19. 00:48

🔺 문제

2644번: 촌수계산

사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어

www.acmicpc.net

🔺 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, M, a, b, cnt;
    static ArrayList<Integer>[] A;
    static int[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());    // 전체 사람 수
        
        // 변수들 초기화
        A = new ArrayList[N + 1];
        for(int i = 1 ; i <= N ; i++) {
            A[i] = new ArrayList<>();
        }
        
        visited = new int[N + 1];
        
        // 촌수 계산할 두 사람 번호
        st = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());
        
        // 데이터 입력받기
        M = Integer.parseInt(br.readLine());
        while(M --> 0) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            
            A[x].add(y);
            A[y].add(x);
        }
        
        bfs(a, b);
        System.out.println(visited[b] == 0 ? -1 : visited[b]);
    }
    
    private static void bfs(int s, int e) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(s);
        
        while(!queue.isEmpty()) {
            int now = queue.poll();
            
            if(now == e)    return;
            
            for(int next : A[now]) {
                if(visited[next] == 0) {
                    visited[next] = visited[now] + 1;    // 🔔 촌수 누적 🔔
                    queue.add(next);
                }
            }
        }
    }
}
Colored by Color Scripter

cs