백준 S2 2644 : 촌수계산 🅾️

[문제]

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

 

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

 

2644번: 촌수계산

 

[풀이]

소요시간 : 33분

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

public class Main {
	static int N; // 사람의 수
	static int start; // 시작하는 사람의 번호
	static int end; // 끝나는 사람의 번호
	
	static List<List<Integer>> list; // 그래프
	static boolean[] check; // 노드 방문 체크용 변수
	static boolean find=false; // 친척 관계 여부
	
	static void dfs(int node, int cnt) {
		if(check[node]) return;
		check[node]=true;
		
		if(node==end) {
			find=true;
			System.out.println(cnt);
			return;
		}
		
		List<Integer> tmp=list.get(node);
		for(int i=0;i<tmp.size();i++) {
			int target=tmp.get(i);
			if(!check[target]) {
				dfs(target, cnt+1);
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		
		N=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine());
		start=Integer.parseInt(st.nextToken())-1;
		end=Integer.parseInt(st.nextToken())-1;
		
		list=new ArrayList<>();
		check=new boolean[N];
		for(int i=0;i<N;i++) {
			list.add(new ArrayList<>());
		}
		
		int M=Integer.parseInt(br.readLine()); // 관계의 수
		for(int i=0;i<M;i++) {
			st=new StringTokenizer(br.readLine());
			int x=Integer.parseInt(st.nextToken())-1;
			int y=Integer.parseInt(st.nextToken())-1;
			list.get(x).add(y);
			list.get(y).add(x);
		}
		
		dfs(start, 0);
		if(!find) System.out.println(-1);
	}

}

 

관계의 깊이 (level)를 구하는 문제였기 때문에 우선 bfs, dfs 중 dfs가 좋을거라 생각했고, dfs 탐색으로 문제를 풀었다.

 

위 코드는 최종 코드인데, 처음 코드를 작성했을 때 테스트케이스를 돌리는데 실패해서 보니 start와 end를 1씩 감소하지 않았었다.

테스트케이스들은 모두 1부터 시작하지만 나는 0부터 시작하기 때문이다. (그래서 x, y는 1씩 감소된 수를 사용한다.)

해서 이 부분을 수정했고, 테스트케이스 2개가 맞길래 돌려보았다. 그랬더니 한 20% 정도 가서 갑자기 실패!

 

뭐가 문제일까 고민해보니 이건 level을 구하는 문제인데 예를 들어 형제자매의 경우 반례가 발생했다.

다음과 같은 테스트케이스가 반례였다.

 

[입력값]

9

7 9

7

1 2

1 3

2 7

2 8

2 9

4 5

4 6

 

이 경우 7과 9는 형제자매로 2촌 관계이기 때문에 2가 출력되어야 하는데 5가 출력됐다.

저때 제출했던 내 틀린 코드의 일부를 발췌하여 보면 이렇다.

static int cnt=0; // 촌 계산
	
static void dfs(int node) {
	if(check[node]) return;
	check[node]=true;
		
	if(node==end) {
		find=true;
		System.out.println(cnt);
		return;
	}
		
	cnt++;
		
	List<Integer> tmp=list.get(node);
	for(int i=0;i<tmp.size();i++) {
		int target=tmp.get(i);
		if(!check[target]) {
			dfs(target);
		}
	}
}

 

7에서 9를 찾는 경우 7 - 2 - 1 - 3 - 8 - 9 순으로 탐색하게 된다.

위의 코드로 탐색하게 되면 cnt는 계속 증가하여 9를 만난 순간 5가 된다.

문제는 7에서 실제 9와의 촌수가 2라는 것이다.

해서 최종 코드를 보면 static 변수인 cnt를 제거하고, 아예 재귀 메소드에서 cnt를 데리고 돈다.

static void dfs(int node, int cnt) {
	if(check[node]) return;
	check[node]=true;
		
	if(node==end) {
		find=true;
		System.out.println(cnt);
		return;
	}
		
	List<Integer> tmp=list.get(node);
	for(int i=0;i<tmp.size();i++) {
		int target=tmp.get(i);
		if(!check[target]) {
			dfs(target, cnt+1);
		}
	}
}

 

이런식으로 다른 level로 넘어가면서 각각의 cnt를 가지고 재귀를 돌기 때문에 실제 level을 계산할 수 있다.

해당 코드로 수정하고 결과는 성공.

 

아쉬운 점이 있기는 하다.

start와 end가 만났을 때 바로 재귀를 끝내고 싶은데 더 도는 경우가 있을 수 있다는 점..