백준 2644 촌수계산 / JAVA

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

2644번: 촌수계산

 

>풀이

/*
 * 백준 2644 촌수계산
 * #실버2
 * #DFS
 */
public class boj_2644 {

	static ArrayList<Integer>[] tree;
	static boolean[] checked;
	static int answer = -1;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 사람 수
		tree = new ArrayList[n+1];
		checked = new boolean[n+1];
		for(int i = 1; i < n+1; i++) {
			tree[i] = new ArrayList<>();
		}
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int x = Integer.parseInt(st.nextToken()); // 계산할사람
		int y = Integer.parseInt(st.nextToken()); // 계산할사람
		int m = Integer.parseInt(br.readLine()); // 부모자식관계 수
		
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			tree[a].add(b);
			tree[b].add(a);
		}
		
		DFS(x,y,0);
		System.out.println(answer);
	}
	
	public static void DFS(int start, int end, int chonsu) {
		if(start == end) {
			answer = chonsu;
			return;
		}
		
		checked[start] = true; // 방문한 사람은 다시방문하지않기위해
		for(int i = 0; i < tree[start].size(); i++) {
			int next = tree[start].get(i);
			if(!checked[next]) {
				DFS(next, end, chonsu+1);
			}
		}
	}
}