문제
부모-자식 관계로 이루어진 가족 관계가 주어진다. 두 사람의 촌수를 계산한다. 촌수는 두 사람 사이의 부모-자식 관계 경로의 수이다. 같은 조상을 통해 연결되지 않은 경우 -1을 출력한다.
입력
첫째 줄에 전체 사람의 수 n이 주어진다. (1 ≤ n ≤ 100)
둘째 줄에 촌수를 계산해야 하는 두 사람 x, y가 주어진다.
셋째 줄에 부모-자식 관계의 수 m이 주어진다.
이후 m줄에 부모 자식 쌍이 주어진다.
출력
두 사람의 촌수를 출력한다. 연결되지 않으면 -1을 출력한다.
예제
입력:
9
7 3
7
1 2
1 3
2 7
2 8
3 4
3 5
4 9출력:
3풀이
핵심 아이디어: 부모-자식 관계를 양방향 그래프로 구성하고, 출발 노드 x에서 목적 노드 y까지 DFS로 탐색하여 경로 길이(촌수)를 구한다.
- 입력된 부모-자식 관계를 양방향 인접 리스트
relation으로 저장한다. - DFS로 x에서 출발하여 y에 도달하면 현재 깊이(cnt)를 결과로 저장한다.
- 방문 체크 배열
checked로 사이클을 방지한다. - DFS 종료 후
res가 -1이면 연결되지 않은 것이므로 -1을 출력한다.
촌수는 최단 경로가 아닌 유일한 경로이므로 DFS/BFS 모두 사용 가능하다.
코드
package com.ssafy.an.day249;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Day200BOJ2644촌수계산DFS {
static List<Integer>[] relation;
static boolean[] checked;
static int res = -1;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
relation = new ArrayList[n + 1];
checked = new boolean[n + 1];
for (int i = 1; i < n + 1; i++) {
relation[i] = new ArrayList<>();
}
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int l = Integer.parseInt(br.readLine());
for (int i = 0; i < l; i++) {
st = new StringTokenizer(br.readLine());
int p = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
relation[p].add(c);
relation[c].add(p);
}
dfs(x, y, 0);
System.out.println(res);
}
static void dfs(int start, int end, int cnt) {
if (start == end) {
res = cnt;
return;
}
checked[start] = true;
for (int i = 0; i < relation[start].size(); i++) {
int next = relation[start].get(i);
if (!checked[next]) {
dfs(next, end, cnt + 1);
}
}
}
}복잡도
- 시간: O(V + E) — 노드 수 V=n, 간선 수 E=m인 그래프 DFS
- 공간: O(V + E) — 인접 리스트 및 방문 배열