[JAVA/BFS] 백준 2644 촌수계산

1. 문제

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

2644번: 촌수계산

 

2. 풀이

BFS를 써서 풀이한다. 처음에는 큐에서 poll 했을때 촌수를 높이는 걸로 처리를 했는데, 그렇게 하면 연결되지 않는(?), 결과에 상관없는 촌수를 계산할 때까지 더하기 처리가 나서 실패했다.

그래서 기준점을 잡아서, 기준점과의 촌수를 계산하는 배열을 따로 만들어 처리했다.

 

3. 코드

 

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.io.*;

public class Main {
    public static int n;
    public static int[][] chons;
        
    // bfs를 사용해 촌수를 계산
    public static int getChon(int a, int b){
        Queue<Integer> q = new LinkedList<>();
        int[] chon = new int[n+1]; // a를 기준으로한 촌수를 저장
        Arrays.fill(chon, -1); // 촌수가 정해지지 않은 상태로 초기화
        
        chon[a] = 0; // 자기자신과의 촌수는 0
        q.add(a);
            
        while(!q.isEmpty()){
            int now = q.poll();
            
            for(int i = 1; i <= n; i++){
                if(chon[i] == -1 && (chons[now][i] == 1 || chons[i][now] == 1)){
                    chon[i] = chon[now] + 1;
                    if(i == b) return chon[i];
                    q.add(i);
                }
            }
        }
            
        return -1;
    }
        
    public static void main (String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);
            
        chons = new int[n+1][n+1];
        int t = Integer.parseInt(br.readLine());
        for(int i = 0; i < t; i++){
            String[] input2 = br.readLine().split(" ");
            int c1 = Integer.parseInt(input2[0]);
            int c2 = Integer.parseInt(input2[1]);
            chons[c1][c2] = 1;
            chons[c2][c1] = 1;
        }
            
        System.out.println(getChon(a, b));
    }
}