[DFS/BFS]문제#1. 촌수 계산(백준 2644번), 자바

2644번: 촌수계산 (acmicpc.net)

DFS를 활용한 촌수 계산하기

import java.util.Scanner;

//백준 2644
//촌수
public class Main {
	
		static int a,b,count,num;
		static int answer=0; 
		public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		//전체 인원 수
		int num=0;
		num=scan.nextInt();
		
		//목표
		a=scan.nextInt();
		b=scan.nextInt();
		
		//관계의 개수
		count=scan.nextInt();
		
		//관계 입력
		int[][] relation=new int[count][2];
		for(int i=0;i<count;i++) {
			relation[i][0]=scan.nextInt();
			relation[i][1]=scan.nextInt();
		}
		
		//visit(방문 경로)
		boolean[] visit=new boolean[count];
	
		//dfs 탐색
		for(int i=0;i<count;i++) {
			if(a==relation[i][0] && !visit[i])
				dfs(relation,visit,relation[i][1],0,i);
			else if(a==relation[i][1] && !visit[i])
				dfs(relation,visit,relation[i][0],0,i);
		}
		if(answer==0) answer=-1;
		System.out.println( answer);
		
	}
	
	static void dfs(int[][] relation, boolean[] visit, int start, int sum, int index) {
		if(start==b) { answer=sum+1; return;}
		//visit 체크
		visit[index]=true;
		
		//target 조건 비교
		if(relation[index][1]==b) { answer=sum+1; return;}
		
		//탐색
		for(int i=0;i<count;i++) {
			if(start==relation[i][0] && !visit[i]) {
				dfs(relation,visit,relation[i][1],sum+1,i);
			}
			if(start==relation[i][1] && !visit[i])
				dfs(relation,visit,relation[i][0],sum+1,i);
		}
	}
}