백준 2644 - 촌수계산

Java

2644 번 - 촌수계산

문제

접근 방법

2차원 배열을 통해 부모 - 자식간의 관계를 나타내었다.

이후 DFS의 그래프 탐색을 통해 주어진 사람을 찾아, 그 사람을 찾기까지 DFS를 호출한 개수를 결과로 반환한다.

중복되어 DFS를 탐색하는 것을 방지하기 위해, 각 사람의 DFS 방문 여부를 나타내는 1차원 배열을 사용하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result = -1, start, end;
	static boolean[] vis;
	static boolean[][] conn;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = stoi(br.readLine());
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	
    	start = stoi(stk.nextToken());
    	end = stoi(stk.nextToken());
    	
    	vis = new boolean[n + 1];
    	conn = new boolean[n + 1][n + 1];
    	
		// 부모, 자식 관계 나타내기
    	int m = stoi(br.readLine()), a, b;
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		
    		conn[a][b] = true;
    		conn[b][a] = true;
    	}
    	
    	DFS(start, 0);
    	
    	System.out.println(result);
    	br.close();
	}
	
	private static boolean DFS(int curN, int cnt) {
		// 한번 방문한 사람이면
		if(vis[curN])
			return false;
		
		// 찾는 사람이면
		if(curN == end) {
			result = cnt;
			return true;
		}
		vis[curN] = true;
		
		for(int i = 1; i <= n; i++) {
			if(conn[curN][i]) {
				if(DFS(i, cnt + 1))	// 찾으면 true를 반환하여 DFS를 조기 종료한다.
					return true;
			}
		}
		return false;
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

개선할 점