1068번: 트리
첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 DFS 카테고리에 있었던 깊이 우선 탐색 방식으로 해결할 수 있었던 문제입니다. 저는 처음에 tree구조를 직접 정의하여 해결하려 했으나 복잡하게 해결하는 것 같아 트리를 구현하는 방식이 아닌 단순하게 리스트에 그래프를 삽입하고 dfs를 이용하여 해결하는 기본적인 방식으로 해결하였습니다.
문제의 예제 2번을 기준으로 설명드리겠습니다. -1 0 0 1 1 인데 0번째 노드는 root노드이므로 따로 빼두고 나머지 경우를 보겠습니다. 그 후 노드 1을 제거합니다. 그 과정은 다음 그림과 같습니다.
  |
좌측은 1을 제거하기전 우측은 1을 제거한 후입니다. 리프 노드가 3개에서 1개로 감소한 것을 알 수 있습니다.
따라서 문제에서 주어진 노드부터 차례차례 삭제를 해 나아간 후(dfs를 응용한 remove함수로 구현) dfs를 이용해 리프 노드의 개수를 세주면 됩니다.
문제 해결을 위한 과정
위의 과정에 단 한가지 예외가 붙는데 바로 루트 노드를 삭제하는 경우입니다. 처음 입력받을 때 루트 노드를 따로 뺀 후 삭제를 시작할 입력받은 노드가 루트 노드라면 바로 0을 출력해주면 됩니다. 이유는 루트 노드를 삭제하는 경우 전체 노드가 없어지기 때문입니다.
소스코드
|
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
33
34
35
36
37
38
39
40
41
42
|
import copy
n = int(input())
graph = [[] for _ in range(n+1)]
data = list(map(int, input().split()))
for i in range(n):
if data[i] == -1: # 부모가 -1인 경우 루트노드로 설정
root = i
continue
graph[data[i]].append(i) # 루트노드가 아닌경우 해당 그래프의 점에 연결
start = int(input())
def dfs(graph, visited, v): # dfs 방식으로 탐색
global count
visited[v] = True # 방문처리
if len(graph[v]) == 0: # 리프 노드의 개수를 셈
count += 1
for i in graph[v]: # 방문처리하지 않은 노드를 재귀의 방식으로 dfs 탐색
if not visited[i]:
dfs(graph, visited, i)
return count
def remove(tempgraph, graph, visited, v): # 입력받은 수의 자식노드를 제거해나가는 함수 dfs 방식 응용
visited[v] = True
for i in range(n): # 그래프를 조회하며 dfs 방식으로 탐색한 노드들을 tempgraph에서 삭제
for j in range(len(graph[i])):
if graph[i][j] == v:
tempgraph[i].remove(v)
for i in graph[v]:
if not visited[i]:
remove(tempgraph, graph, visited, i)
if start != root: # 지우기 시작할 노드가 root가 아닌경우
tempgraph = copy.deepcopy(graph) # graph를 복사하여 tempgraph생성
count = 0
visited = [0] * (1 + n)
remove(tempgraph, graph, visited, start)
count = 0
visited = [0] * (1 + n)
print(dfs(tempgraph, visited, root))
else: # 지우기 시작할 노드가 root인 경우 그냥 0을 출력함
print(0)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 13549: 숨바꼭질 3(Python) (0) | 2021.02.25 |
|---|---|
| 백준 알고리즘 1504: 특정한 최단 경로(Python) (0) | 2021.02.23 |
| 백준 알고리즘 1074: Z(Python) (0) | 2021.02.20 |
| 백준 알고리즘 13459: 구슬 탈출(Python) (0) | 2021.02.19 |
| 백준 알고리즘 13460: 구슬 탈출 2 (Python) (1) | 2021.02.19 |