[백준] 2644. 촌수계산 (Java)

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

2644번: 촌수계산

 

문제 설명

가족들 사이의 관계를 촌수로 표현한다.

촌수를 계산할 때는, 부모와 자식 사이를 1촌으로 정의하고, 이로부터 사람들 간의 촌수를 계산한다.

 

ex) 나와 아버지 (1촌), 아버지와 할아버지 (1촌)으로 나와 할아버지는 (2촌)이 되고, 아버지 형제들과 할아버지는 (1촌), 나와 아버지 형제들과는 (3촌)이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

/* 입력 예시 */

9 //전체 사람 수 
7 3 //촌수를 계산해야 하는 서로 다른 두 사람의 번호
7 // 부모 자식들 간의 관계의 개수
1 2 //부모 자식간의 관계 ↓
1 3
2 7
2 8
2 9
4 5
4 6

---

💡 아이디어

촌수를 계산하는 방법은 연결되어 있는 부모 자식 간의 관계를 통해 시작부터 도착까지 거리를 계산하는 것과 같습니다.

따라서 BFS를 사용해 구한다면 쉽게 구할 수 있습니다.

 

📗 풀이과정

1. 관계를 저장할 HashMap을 만들고, 그 안에 i번째 사람과의 관계를 집어넣기 위해 ArrayList를 넣습니다.

static Map<Integer,ArrayList<Integer>> family = new HashMap<>(); //가족 관계

 

2. 입력받은 전체 사람 수를 변수에 저장해주고, 사람 수만큼 family 관계를 저장할 공간을 만들어 줍니다.

int people = Integer.parseInt(br.readLine());//전체 사람 수

for(int i=1;i<=people;i++) family.put(i, new ArrayList<>());

 

3. 촌수를 계산해야 하는 사람 번호를 start, end변수에 저장해 주고, 모든 부모자식 간의 관계를 family에 저장합니다.

String[] s = br.readLine().split(" ");
int start = Integer.parseInt(s[0]);//출발
int end = Integer.parseInt(s[1]);//도착
		
int n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++) {
    //받아온 두 개의 숫자를 int[]배열에 넣어줌.
    int[] connect = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

    family.get(connect[0]).add(connect[1]);
    family.get(connect[1]).add(connect[0]);
}

 *** 원래 위의 start와 end를 구할 때 처럼 connect 변수 두 개를 구해줘도 되지만 Stream을 이용해 구현하였습니다. ***

 

 

4. 촌수를 계산하는 BFS를 구현해주고, start값이 end값을 만나 해당 촌수 값을 return 하도록 합니다.

(전체 코드 참고)

 

---

전체 코드

import java.io.*;
import java.util.*;
import java.util.stream.Stream;

public class Main {
	static Map<Integer,ArrayList<Integer>> family = new HashMap<>(); //부모 자식 간의 관계
	static boolean[] visited;//방문처리
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int people = Integer.parseInt(br.readLine());//전체 사람 수
		
		for(int i=1;i<=people;i++) family.put(i,new ArrayList<>());
		
		String[] s = br.readLine().split(" ");
		int start = Integer.parseInt(s[0]);//출발
		int end = Integer.parseInt(s[1]);//도착
		
		int n = Integer.parseInt(br.readLine());
		for(int i=0;i<n;i++) {
			//받아온 두 개의 숫자를 int[]배열에 넣어줌.
			int[] connect = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
			
			family.get(connect[0]).add(connect[1]);
			family.get(connect[1]).add(connect[0]);
		}
		visited = new boolean[people+1];
		
		System.out.println(bfs(start,end));
		
	}
	static int bfs(int start, int end) {
		
		int degree=-1;//촌수 -> 만약 촌수 계산할 수 없으면 -1 return.
		
		Queue<int[]> q = new LinkedList<>();
		q.offer(new int[] {start,0});
		visited[start]=true;//방문처리
		
		while(!q.isEmpty()) {
			int[] now = q.poll();
			
			//end에 도착하면 해당 촌수값을 degree에 넣어 종료.
			if(now[0]==end) { degree=now[1];break;}
			
			for(int i:family.get(now[0])) {//now[0]에 연결된 관계들 가져옴.
				if(visited[i]) continue;
				
				visited[i]=true;
				q.offer(new int[] {i,now[1]+1});
			}
		}
		return degree;
	}
}