[백준 2664] 촌수계산 (C++, Java)

www.acmicpc.net/problem/2644

2644번: 촌수계산

 

문제풀이

(7)	(3)
2	1
1

• 노드 짜는 문제...!
• 노드 (부모, 자식) 중요 
  • 조상, 자식 개념으로 생각하는게 맞을듯...
  • 출발 부터 조상은 여러명이 될 수있음.
• 각각 서로 같은 조상을 만났을 때
  • 직속 : 본인(person1)과 목적지(person2)가 서로 할아버지->아버지->나 이런 관계 일때 ex) 7-2 관계
  • 직속으로 만났을 땐 해당 인덱스 +1 해준다. 
  • 직속이 아닐 경우 각각의 인덱스에서 +2 해준다. +2 란 가는 경로를 다 더해주는 느낌이다.
• 입력 받아오는 것 노드 연결 까지 입력 코테에서는 가장 좋은 문제

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct aaa
{
	int p;
	vector<int> v;
};
aaa ar[10001];
int num1,num2;
int ans;
int cnt;

void input()
{
	int numSize;
	cin >> numSize;
	for(int i =0 ; i < numSize; i++)
	{
		int a, b;
		cin >> a >> b; //1,2 
		ar[a].v.push_back(b);
		ar[b].p = a;
	}

}

void dfs(int n)
{
	int temp;
	temp = ar[n].p;
	if (n == ans || ans ==-1 ||temp ==0)
	{
		return;
	}
	cnt++;
	
	
	if (temp != 0)
		dfs(temp);
	else
		return;
}
void solve()
{
	vector<int> vv[2];
	//ROOT 이면..
	if (ar[num1].p == 0 && ar[num1].v.size() == 0)
		return;
	if (ar[num2].p == 0 && ar[num2].v.size() == 0)
		return;
	vv[0].push_back(num1);
	int x =num1;
	while (1)
	{
		if (ar[x].p == 0) //즉 부모가 없으면 
		{
			//vv[0].push_back(0);//부모삽입
			break;
		}
		vv[0].push_back(ar[x].p);//부모삽입
		x = ar[x].p;  // x를 부모로 바꿈 그 부모를 찾기위해  따라서 v[1]에는 부모들이 쌓임 
	}
	vv[1].push_back(num2);
	int y =num2 ;
	while (1)
	{
		if (ar[y].p == 0)
		{
			break;
		}
		vv[1].push_back(ar[y].p); //두번째숫자의 부모들 넣음
		y = ar[y].p; //부모 체인지  맨끝까지 올라감 
		//즉 3,7은 각자의 맨끝인 1까지 삽입 
	}
	
	
	

	for (int i = 0; i < vv[0].size(); i++)
	{
		
		bool flag = false;
		int res;
		for (int j = 0; j< vv[1].size(); j++)
		{
			if (vv[0][i] == vv[1][j])
			{
				res = vv[0][i];
				flag = true;
				break;
			}
			/*else 
			{
				ans = -1; //조상이 같지 않음! 남남
			}*/
			
		}

	//	sort(vv[0].rbegin(), vv[0].rend());
//		sort(vv[1].rbegin(), vv[1].rend());

		if (flag == true) //조상을 찾았다면!
		{
			//추가
			for (int w = 0; w < vv[0].size(); w++)
			{
				cnt++;
				if (vv[0][w] == res)
				{
					break;
				} 
			}
			for (int w = 0; w < vv[1].size(); w++)
			{
				cnt++;
				if (vv[1][w] == res)
				{
					break;
				}
			}
			cnt -= 2;
			break;
		}
	}
 
}

int main()
{
	int tm;
	cin >> tm;
	cin >> num1 >> num2;
	input();
	solve();
	if (cnt == 0)
	{
		cnt = -1;
	}
	cout << cnt << endl;
	return 0;
}

 

Java

package Z_ShinHanCard_Prepare;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node_Family
{
	int parent;
	ArrayList<Integer> child;
	int level;
	public Node_Family(int parent, ArrayList<Integer> child, int level) {
		super();
		this.parent = parent;
		this.child = child;
		this.level = level;
	}
	 
}

public class D2백준2644_촌수계산_DFSBFS_노드 {
	static Node_Family family[] =new Node_Family[101];
	static int answer ;
	static void solve(int person, int person2)
	{
		int x = person;  //7 
		ArrayList<Integer> [] arr= new ArrayList[2];
		Queue<Integer>que= new LinkedList<Integer>();
		for (int i=0; i<2;i++) 
		{
			arr[i]= new ArrayList<Integer>();
		}
		//node1의 부모탐색 즉 7의 부모탐색 
		while(true)
		{
			//부모가 더이상없다면 끝내 처음에 0으로 생성함.
			if(family[x].parent==0)
				break;
			//아니면 arr[0]리스트에 부모들을 다 더해준다. 아버지+할아버지
			arr[0].add(family[x].parent);
			x= family[x].parent; 
		}
		//숫자 3에 조상 다 구하기
		x= person2;
		while(true)
		{
			if(family[x].parent==0)
				break;
			arr[1].add(family[x].parent);
			x= family[x].parent;
		}
		//첫놈의 조상 중에 둘째 놈이 있다면 ?
		if(arr[0].contains(person2))
		{
			// [0][0] 있다면 1촌 [0][1]에 있다면 2촌
			answer= arr[0].indexOf(person2)+1;
		}else if (arr[1].contains(person))
			answer =arr[1].indexOf(person)+1;
		else
		{
			boolean flag = false;
			for(int i = 0 ; i<arr[0].size();i++)
			{	for(int j = 0 ; j < arr[1].size(); j++)
				{
					if(arr[0].get(i)==arr[1].get(j) )
					{
						answer = i+j +2;
						flag=true;
						break;
					}
				}
				if(flag)
					break;
			}
			
			if(!flag)
			{
				answer = -1; 
			}
		}
		
	}
	
	
	public static void main(String[] args) throws Exception 
	{
		/*
		 *  9 //전체사람수 9명 
			7 3 //7과 3은?
			7   //관계 7
			1 2
			1 3
			2 7
			2 8
			2 9
			4 5
			4 6
		 * */
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		int m= Integer.parseInt(br.readLine()); //총 인원 : 9
		String input= br.readLine(); //누구누구?  7,3 
		StringTokenizer st= new StringTokenizer(input);
		int person= Integer.parseInt(st.nextToken()); //7
		int person2= Integer.parseInt(st.nextToken());//3
		// TODO Auto-generated method stub
		int e= Integer.parseInt(br.readLine()); //7번 !
		for(int i = 0 ; i<family.length;i++)
		{
			family[i] =new Node_Family(0,new ArrayList<Integer>(), 0);
		}
		for(int i =0 ; i <e ; i++)
		{
			input =br.readLine();//1,2 -> 1,3 
			st= new StringTokenizer(input);
			int node1= Integer.parseInt(st.nextToken()); //1
			int node2=Integer.parseInt(st.nextToken()); //2
			//1의 자식 2라는 뜻 1의 자식이 여러명 일수 있으니 array리스트로 구현 C++ 이었으면 vector
			family[node1].child.add(node2);  
			family[node2].parent=node1;  //2의 부모는 1이라는 
		}
		
		solve(person,person2); // 7,3 목적지 
		System.out.println(answer);	
		

	}

}