[Python][백준 19641][DFS] 중첩 집합 모델 - 컴도리돌이

반응형

19641번: 중첩 집합 모델

---

풀이 과정

만약 문제가 잘 이해 안 된다면 표를 잘 보시면 됩니다. 

😊

 

표의 예시에서 "HI-ARC"가 root 노드로 시작됩니다. 

그러기 때문에 root 노드 "HI-ARC"의 왼쪽 노드는 order을 1로 가집니다.

 

그 이후에 "HI-ARC"와 연결된 노드를 찾습니다. 

표에서는 "경영 지원실"이 제일 빠른 노드입니다.

해당 "경영 지원실"의 왼쪽 노드는 다음 order인 2를 가집니다.

 

"경영 지원실"과 연결된 노드... 노드... 연결된 노드...

쭉쭉 가다가

"사원 1"로 가보면 해당 "사원 1"과 연결된 노드가 없습니다.

"사원 1"에서 왼쪽 노드의 order 값을 4를 가졌는데,

연결된 노드가 없기 때문에 오른쪽 노드로 바로 가서

order 값을 5로 할당받고 "사원 2"로 돌아갑니다.

 

이제 좀 이해가 가셨나요? 🥲

즉 root 노드부터 자식 노드의 자식 노드의 자식... 의 왼쪽 노드 값이 1, 2, 3,.... n으로 가다가

연결된 노드가 없으면 해당 자식 노드의 오른쪽 노드의 값은 n+1 

이런 식으로 구현해주시면 됩니다.

 

 

1. 간선의 정보를 graph에 저장하였다. graph에 간선 정보를 저장할 때 

번호가 낮은 노드부터 방문하기 때문에 정렬시켜서 저장하였다.

 

2. 해당 문제는 left, right가 있기 때문에 tree 형태로 데이터를 저장하기 위해서

(n+1)만큼 사이즈로 사이즈가 2인 배열을 "tree"에 저장하였다.

 

3. dfs 탐색

3-1 ) 현재 노드의 왼쪽 노드(tree [cur][0])에 현재 order을 저장한다.

3-2) 현재 노드와 연결된 노드를 dfs에 탐색한다.

3-3) 다음 노드의 탐색을 마치고 현재 노드의 오른쪽 노드의 order 값을 order+1을 해준다.

3-4) 해당 order+1을 반환해준다.

---

풀이 코드

import sys; input = sys.stdin.readline ; sys.setrecursionlimit(10**6)
def dfs(cur,order) :
  tree[cur][0] = order
  for next in graph[cur] :
    if tree[next][0] : continue
    order = dfs(next,order+1)
  tree[cur][1] = order + 1
  return order+1
  
n = int(input())
graph = [None for i in range(n+1)]

for _ in range(n) :
  v,*arr = map(int,input().split())
  graph[v] = sorted(arr[:-1])

root,order,tree = int(input()),0,[[0,0] for i in range(n+1)]
dfs(root,1)
for i in range(1,n+1) : print(i,tree[i][0],tree[i][1])