DFS11 [백준] 11725번 - 트리의 부모 (파이썬) 문제) 백준 - 트리 (Tree) - 트리의 부모 -> www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 트리 상에서 연결된 두 정점을 인접 리스트 방식으로 나타낸다. 문제에서 트리의 루트가 1번으로 주어졌으므로 dfs를 이용해 1번부터 시작해 노드에 연결된 노드들을 순회한다. parent 리스트에 부모를 채킹(Checking)하면서, 0일 겨우 방문하지 않은 노드로 인식해 부모 노드로 저장한다. 소스 코드) import sys sys.setrecursionlimit(10 ** 8) n = int(input()) tree .. 2021. 3. 12. [백준] 1068번 - 트리 (파이썬) 문제) 백준 - 그래프 이론/트리 - 트리 -> www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 인접 행렬 방식으로 graph를 False로 초기화한다. 2. 입력으로 들어온 부모 노드들의 정보를 이용해 graph의 연결을 채워주고 root를 선정한다. 3. 세 번째 줄 입력에 나오는 지울 노드의 모든 연결을 끊어준다.(False로 설정) 4. dfs로 root부터 탐색해 리프 노드 개수를 구해준다. 반성) 트리 문제라 생각해서 인접 행렬의 활용과.. 2021. 2. 20. 이전 1 2 다음 반응형
