[백준 알고리즘] 2644 촌수계산(with Java)

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

주어진 문제의 촌수를 계산하는 문제이다.

문제에 예시로 주어진 경우를 트리로 표현하면 다음과 같다.

문제는 이 트리에서 문제에 주어진 두 숫자의 관계가 몇촌인지를 계산하는 것이다.

문제풀이.

먼저 두 숫자의 부모를 모두 찾아서 두개의 array에 담았다.

그리고 이 두개의 array를 순서대로 비교하여 동일한 숫자가 나오는 index값을 찾아서 

그 두개의 index를 더해주면 두 숫자의 촌수가 된다.

예를 들어,

7의 부모는 7을 포함하여 arrayA = 7,2,1

3의 부모는 3을 퐇마하여 arrayB = 3,1

7과 3의 부모를 저장한 위의 두 arrayA와 arrayB를 순차적으로 탐색했을 때 공통된 숫자는 1.

arrayA에서 1의 index는 2, arrayB에서 1의 index는 1이다.

이 두개의 인덱스 2와 1의 합은 3.

두 숫자의 촌수는 3이다.

import java.util.ArrayList; import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); // 사람숫자 int n = sc.nextInt(); // 문제 int a = sc.nextInt(); int b = sc.nextInt(); // 링크갯수 int m = sc.nextInt(); // 관계 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i < m; i++) { int value = sc.nextInt(); // 부모 int key = sc.nextInt(); // 자식 map.put(key, value); } ArrayList<Integer> alist = new ArrayList<Integer>(); ArrayList<Integer> blist = new ArrayList<Integer>(); alist.add(a); blist.add(b); for(int i = 1; i <= m; i++) { Integer parent = map.get(a); if(parent == null) { break; }else { alist.add(parent); a = parent; } } for(int i = 1; i <= m; i++) { Integer parent = map.get(b); if(parent == null) { break; }else { blist.add(parent); b = parent; } } int rslt = -1; for(int i = 0; i < alist.size(); i++) { for(int j = 0; j < blist.size(); j++) { if(alist.get(i).equals(blist.get(j))) { rslt = i+j; break; } } if(rslt != -1) { break; } } System.out.println(rslt); } }