[백준] 2644 촌수계산 - Graph Theory / Java

• 문제 링크

2644번: 촌수계산

 

• 풀이 과정

문제에 제시된 촌수는 연결 요소에서 특정 두 정점 간 도달하기 위한 간선의 개수를 의미한다.

 

정점의 개수, 거리를 계산할 두 정점, 그리고 무향 그래프 정보를 입력받아 인접 리스트로 구현한다.

시작 정점을 지정해 dfs 탐색을 수행할 함수에 매개변수로 전달하고,

간선을 따라 이동한 횟수를 나타낼 cnt 변수를 매개변수로 0으로 초기화하여 생성한다.

 

방문 여부를 확인하는 boolean 배열을 활용하여 연결된 모든 정점을 탐색하며

다음 정점을 이동할 시 해당 정점과 현재까지 이동한 횟수에 1를 더한 값을 매개변수로 재귀 호출한다.

 

이때 이동한 정점이 도착 정점이라면 -1 로 초기화되어 있는 result 변수에 cnt 변수를 대입하고 함수를 빠져나온다.

즉 촌수를 계산할 수 없을 시 -1 로 출력되고 그 외의 경우 대입된 값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static List<List<Integer>> list = new ArrayList<>();
	static boolean[] visit;
	static int dest; 
	static int result = -1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		int n = Integer.parseInt(br.readLine());
		visit = new boolean[n + 1];

		for (int i = 0; i < n + 1; i++)
			list.add(new ArrayList<>());

		st = new StringTokenizer(br.readLine());
		int root = Integer.parseInt(st.nextToken());
		dest = Integer.parseInt(st.nextToken());

		int m = Integer.parseInt(br.readLine());
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			list.get(x).add(y);
			list.get(y).add(x);
		}

		dfs(root, 0);

		bw.write(result + "\n");
		bw.flush();
	}

	private static void dfs(int node, int cnt) {
		if (node == dest) {
			result = cnt;
			return;
		}
			
		visit[node] = true;
		for (int next : list.get(node)) {
			if (!visit[next]) 
				dfs(next, cnt + 1);
		}
	}

}