백준 2644번 촌수계산

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

2644번: 촌수계산

전형적인 dfs연습문제였다. 문제들을 bfs로 많이 풀다보니 자연스럽게 bfs로 풀려고 하는 것 같은데, 이처럼 단순한 문제는 dfs로 풀어보려는 노력을 해야겠다.

그래도 dfs 까먹거나 그런건 아니니 다행!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class bj2644 {
	static int N;
	static int A,B;
	static boolean [][] edge;
	static boolean [] visit;
	static int result=987654321;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		A = Integer.parseInt(st.nextToken());
		B = Integer.parseInt(st.nextToken());
		int input = Integer.parseInt(br.readLine());
		edge = new boolean[N+1][N+1];
		visit = new boolean[N+1];
		for(int i=0;i<input;i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			edge[a][b]=true;
			edge[b][a]=true;
		}
		dfs(A,0);
		if(result==987654321)
			System.out.println(-1);
		else 
			System.out.println(result);
	}
	static void dfs(int nowIndex,int level){
		visit[nowIndex] = true;
		if(nowIndex == B) {
			result = Math.min(result, level);
			return;
		}
		for(int i=1;i<N+1;i++) {
			if(visit[i]) continue;
			if(!edge[nowIndex][i]) continue;
			dfs(i,level+1);
		}
	}
}