BOJ - 2644 ) 촌수계산

---

 

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

2644번: 촌수계산

---

주어진 두 노드간에 촌수를 계산하는 기본적인 BFS문제이다.

 

나와 연결된 노드는 1촌의 관계를 가지며 

 

주어진 두 노드간의 거리를 구하는 문제였다.

 

BufferedReader 사용법이 익숙하지 않아서 

새로운줄을 받을때에 토크나이저를 계속 새로 만들어주었는데 이부분을 개선해야겠다.

---

 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;
 
class node{
    int no;
    int depth;
    node(int no, int depth){
        this.no = no;
        this.depth = depth;
    }
}
public class Main {
    static int map[][] = new int[101][101];
    static boolean visit[]= new boolean[101];
    public static void main(String[] args) throws Exception {
        int ans = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n  = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int m =  Integer.parseInt(st.nextToken());
        while(m >0) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int x = Integer.parseInt(st.nextToken());
            map[y][x] = 1;
            map[x][y] = 1;
            m--;
        }
        if(start == end) System.out.println(0);
        else {
            Deque<node> dq = new ArrayDeque<node>();
            dq.add(new node(start,0));
            visit[start] = true; 
            while(!dq.isEmpty()) {
                node now = dq.poll();
                if(now.no == end) {
                    ans = now.depth;
                    break;
                }
                for(int index = 0; index < n +1 ; index++) {
                    if(map[now.no][index]==0) continue;
                    if(map[now.no][index]==1 && !visit[index]) {
                        visit[index] = true; 
                        dq.add(new node(index,now.depth+1));
                    }
                }
                
                
            }
            if(ans ==0) System.out.println(-1);
            else System.out.println(ans);
        }
    }
 
}
 

---