[백준] 2644번 : 촌수 계산 자바(JAVA) 풀이

문제

---

https://www.acmicpc.net/problem/2644 

---

문제 탐색하기

• n : 전체 사람의 수
• start, end : 촌수를 계산해야하는 서로 다른 두 사람
• m : 부모 자식들 간 관계 개수
• x, y : 관계를 나타내는 수 (x는 y의 부모)
• 촌수를 계산하는 것은 이어진 그래프에서 깊이 차이 구하기이므로 DFS 이용
• 어떤 사람부터 탐색을 시작해도 깊이를 구할 수 있도록 양방향 간선으로 입력받음

 

DFS 탐색

1. start 부터 탐색 시작
2. 탐색 중 end를 만나는지 확인
3. 만났을 경우 깊이 값 출력

 

가능한 시간복잡도

입력 범위 ( 1 ≤ n ≤ 100)

1. 그래프 생성 
   • n : 전체 사람의 수 (그래프의 노드 수)
   • m : 부모-자식 간의 관계 개수 (그래프의 간선 수)
   • 부모-자식 관계를 입력받고, 그래프를 구성할 때, m개의 간선을 입력받으므로 시간 복잡도 O(m)
2. DFS 탐색
   • 한 노드를 방문하고, 그 노드와 연결된 모든 간선을 탐색하므로 시간 복잡도 O(n + m)
3. 전체 시간 복잡도 시간 복잡도 O(n + m)

---

헷갈렸던 부분

촌수를 계산할 때 재귀함수를 호출하기 전에 count++ 하는 거랑 dfs의 파라미터로 cnt+1를 넘겨주는 거랑 같다고 생각을 했었는데 완전 다른 경우였다.

1. cnt+1 (올바른 경우)
   • 재귀 호출 시 함수의 매개변수로 증가한 값을 넘김
   • cnt는 현재 함수 호출에서만 유효한 지역 변수로, dfs 함수가 호출될 때마다 재귀 호출마다 독립적인 값으로 전달됨.
   • 값은 재귀가 끝날 때 해당 호출이 끝나면서 사라짐 => 각 경로에서 촌수를 독립적으로 계산 가능
2. count ++ (틀린 경우)
   • 전역 변수의 값을 직접 증가시킴
   • DFS 탐색 과정에서 어떤 경로를 탐색해도 값이 증가됨
   • 한 경로의 탐색이 끝나지 않았음에도 다른 경로에서 값이 증가함

static void dfs(int start, int end, int cnt) {
        // 촌수 계산 끝난 경우
		if(start == end) {
			count = cnt;
			return;
		}
		
		visited[start] = true;
		
		for(int next:graph.get(start)) {
			if(!visited[next]) {
            	// count ++;
				dfs(next, end, cnt +1);
                // 재귀 호출마다 독립적으로 값을 증가시키기 위해 cnt 값 넘겨줌
			}
		}		
	}

---

코드 설계하기

• 입력받는 값을 인접리스트를 사용해 저장한다.
• 어느 방향에서도 촌수를 계산할 수 있도록 양방향으로 저장한다.
• 재귀 호출마다 독립적으로 값을 증가시키기 위해서 cnt+1 값을 넘겨준다.
• 탐색이 끝나면 메소드를 종료시키고 값을 출력한다.

---

풀이 코드

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

public class Main {
	
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	static int count = -1;
		
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine()); // 전체 사람의 수
		
		visited = new boolean[n+1];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());
		
		int m = Integer.parseInt(br.readLine()); // 부모 자식들 간 관계 개수
		
		graph = new ArrayList<ArrayList<Integer>>();
		for(int i=0;i<n+1;i++) {
			graph.add(new ArrayList<Integer>());
		}
		
		// 부모 자식간의 관계를 인접리스트로 저장
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			// 양방향으로 저장
			graph.get(x).add(y);
			graph.get(y).add(x);
		}
		
		dfs(start, end, 0);
		
		System.out.println(count);
	}
	
	static void dfs(int start, int end, int cnt) {
        // 촌수 계산 끝난 경우
		if(start == end) {
			count = cnt;
			return;
		}
		
		visited[start] = true;
		
		for(int next:graph.get(start)) {
			if(!visited[next]) {
				dfs(next, end, cnt +1);
                // 재귀 호출마다 독립적으로 값을 증가시키기 위해 cnt 값 넘겨줌
			}
		}		
	}
}