[BOJ] 2644 촌수계산

문제

www.acmicpc.net/problem/2644

2644번: 촌수계산

풀이

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

public class Main {
    static boolean[][] cs;
    static boolean[] visited;
    static int cnt=-1;
    static void cs_dfs(int st, int dt, int N, int c) {
    	if(st==dt) {
    		cnt = c;
    		return;
    	}
    	for(int i=1;i<N+1;i++) {
    		if(cs[st][i] && !visited[i]) {
    			visited[i] = true;
    			cs_dfs(i,dt,N,c+1);
    			visited[i] = false;
    		}
    	}
    }
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, cp1,cp2,m;
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine()," ");
        cp1 = Integer.parseInt(st.nextToken());
        cp2 = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(br.readLine());
        cs = new boolean[N+1][N+1];
        visited = new boolean[N+1];
        for(int i=0;i<m;i++) {
        	st = new StringTokenizer(br.readLine()," ");
        	int from = Integer.parseInt(st.nextToken());
        	int to = Integer.parseInt(st.nextToken());
        	cs[from][to] = cs[to][from] = true;
        }
        
        cs_dfs(cp1,cp2,N,0);
        System.out.println(cnt);
    }
}