728x90
문제
트리가 주어지고, 두 노드 X, Y가 주어질 때, 이 두 노드 사이의 거리를 출력하는 프로그램을 작성하시오. 트리에서는 두 노드를 잇는 경로가 유일하기 때문에, 정답은 항상 유일하다는 것을 참고한다. 예를 들어, 다음과 같은 트리에서 노드 3, 노드 6 사이의 거리는 4이다.
입력
첫 번째 줄에 트리의 노드 개수 n, 두 노드 X, Y의 번호가 주어진다. ( 0 ≤ X, Y ≤ n < 1000 ) 두 번째 줄부터 트리의 간선 정보가 주어진다. 각 줄은 2개의 숫자 a, b로 이루어지며, 이는 노드 a가 노드 b의 부모노드라는 것을 의미한다. 루트는 노드 0이라고 가정한다.
출력
두 노드 X, Y 사이의 거리를 출력한다.
예제 입력
11 3 6
0 1
0 2
1 3
1 4
1 5
2 6
2 10
6 7
6 8
6 9
예제 출력
4
#코드 : 왜 틀릴까?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
import sys
# 노드 a가 노드 b의 부모노드라는 것을 의미한다.
# 루트는 노드 0이라고 가정한다.
def getResult(dist, idx):
# dist : 루트부터 해당 값의 레벨을 가진다.
global arr, start_idx, end_idx, x, y
if len(arr[idx]) > 0:
for i in range(len(arr[idx])):
if arr[idx][i] == x:
start_idx = dist
if arr[idx][i] == y:
end_idx = dist
getResult(dist+1, arr[idx][i])
if __name__ == "__main__":
input = sys.stdin.readline
n, x, y = map(int, input().split())
arr = [[] for _ in range(n)]
# start_idx : 루트부터 해당 x값 까지의 레벨
# end_idx : 루트부터 해당 y값 까지의 레벨
start_idx, end_idx = 0, 0
for i in range(n-1):
a, b = map(int, input().split())
arr[a].append(b)
if len(arr) > 0:
getResult(1, 0)
print(start_idx + end_idx)
|
cs |
#코드 : 통과
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
import sys
# 노드 a가 노드 b의 부모노드라는 것을 의미한다.
# 루트는 노드 0이라고 가정한다.
def getResult(x, idx):
global data, max_level, visited, y
# x는 레벨, idx는 해당위치의 값을 가지고 깊이를 탐색하는 메서드
if idx == y:
max_level = x
return
for i in range(len(data[idx])):
if not visited[idx]:
visited[idx] = True
getResult(x+1, data[idx][i])
visited[idx] = False
if __name__ == "__main__":
input = sys.stdin.readline
max_level = 0
n, x, y = map(int, input().split())
get_data = [list(map(int, input().split())) for _ in range(n)]
data = [[] for _ in range(len(get_data))]
visited = [False]*(n+1)
for i in range(len(get_data)):
if len(get_data[i]) > 0:
data[get_data[i][0]].append(get_data[i][1])
data[get_data[i][1]].append(get_data[i][0])
if len(data) > 0:
getResult(0, x)
print(max_level)
|
cs |
반응형