백준 : 2644 (촌수 계산) (DFS)

이번문제는 촌수 계산만 잘 적용하면, 기존 BFS 문제들과 비슷하다고 볼 수 있다.

if(visited[tmp] == false) { //아직방문전
     dist[tmp] = dist[now]+1; // 촌수 계산
     dfs(tmp, end); //재귀
}

 

import java.util.*;

class Main {

	static int n, m, start, end;
	static boolean[] visited;
	static int[] dist;
	static ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();

	public static void dfs(int now, int end) {
		visited[now] = true; //방문표시
		
		for(int i=0; i< graph.get(now).size(); i++) {
			int tmp = graph.get(now).get(i);
			
			if(visited[tmp] == false) { //아직방문전
				dist[tmp] = dist[now]+1; // 촌수 계산
				
				dfs(tmp, end);
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt(); 
		sc.nextLine();
		
		String st = sc.nextLine(); 
		String[] stArr = st.split(" ");
		start = Integer.parseInt(stArr[0]);
		end = Integer.parseInt(stArr[1]);
		
		m = sc.nextInt(); 
		sc.nextLine();
		
		//초기화
		visited = new boolean[n+1];
		dist = new int[n+1];
		for (int j = 0; j < n+1; j++) { //인덱스 0 사용안함 주의*****
			graph.add(new ArrayList<Integer>());
		}

		//그래프 입력
		for (int j = 0; j < m; j++) { 
			st = sc.nextLine(); 
			stArr = st.split(" ");	
			
			int a = Integer.parseInt(stArr[0]);
			int b = Integer.parseInt(stArr[1]);
			
			graph.get(a).add(b);
			graph.get(b).add(a); //양방향*****
		}
		
		dfs(start, end);
		
		System.out.println(dist[end] == 0? -1 : dist[end]); //불가능 처리
	}
}