백준 2644번 : 촌수계산

 문제

www.acmicpc.net/problem/2644

2644번: 촌수계산

2644 촌수계산

 

 구현 방법

 인접리스트 생성해서 dfs로 구현하였습니다.

찾아야할 값 둘 중 하나는 찾으러 갈 타켓, 하나는 찾을 값으로 지정한 후 깊이로 +1 씩 카운팅을 해주었습니다.

ans를 -1로 초기화하고 해당 값을 찾으면 카운팅 값 저장 후 return, 못 찾으면 ans를 그대로 출력해주었습니다.

 

 구현 코드

package BOJ.silver;

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

public class B2644_촌수계산 {
	static List<List<Integer>> dfs;
	static int find1, find2, N, M, ans;
	static boolean[] visit;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		visit = new boolean[N+1];
		dfs = new ArrayList<>();
		StringTokenizer st = new StringTokenizer(br.readLine());
		find1 = Integer.parseInt(st.nextToken());
		find2 = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(br.readLine());
		for (int i=0;i<=N;i++) {
			dfs.add(new ArrayList<>());
		}
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			dfs.get(x).add(y);
			dfs.get(y).add(x);
		}
		// 입력 완료
		ans = -1;
		dfsL(find1, find2, 0);
		System.out.println(ans);
	}
	
	static void dfsL(int target, int find2, int cnt) {
		visit[target] = true;
		
		int size = dfs.get(target).size();
		for (int i=0;i<size;i++) {
			int value = dfs.get(target).get(i);
			if(!visit[value]) {
				if (value==find2) {
					ans = cnt+1;
					return;
				}
				else dfsL(value, find2, cnt+1);
			}
		}
		return;
	}
}

 

정답!