[코테] 백준 11725번 문제 풀이 - 트리 부모 찾기

코테 공부하는 건 처음이라 머릿속 알고리즘을 코드로 풀어 쓰는게 생각보다 어려웠다.

그래서 한 문제 푸는데 정말 오래 걸렸다..

 

 

문제

---

https://www.acmicpc.net/problem/11725

 

 

 

 

접근

---

이 문제는 트리속 각 정점의 부모를 찾는 문제이다. 

그럼 트리는 뭘까..?

 

😎 트리

• 그래프의 여러 구조 중 단방향 그래프의 한 구조
• 하나의 뿌리로부터 가지가 사방으로 뻗은 형태. 사이클이 없는 하나의 연결 그래프
• 예 : 컴퓨터 디렉터리 구조, 가족관계도

6 3  →    1

1 2         / \

1 3        2  3

2 4        |

0 0       4

 

• 정점 1개도 트리 1개로 침
• 정점 1개도 트리로 치는 점은 사이클과 비슷함

 

 

7
1 6
6 3
3 5
4 1
2 4
4 7

 

문제에 나온 예제를 트리로 만들어 보면

 

  1

 / \

6    4

|    / \

3  2   7

|

5

 

이렇게 된다!

1. 1이 루트니, 1이 있는 그룹을 찾아서 그룹 내 1 이외 숫자(6, 4)의 부모로 1을 저장하고, 숫자를 기억해둔다.

2. 6이 있는 그룹을 찾아서 그룹 내 6 이외의 숫자의 부모로 6을 저장하고, 숫자를 기억해둔다.

3. 3이 있는 ...

...

4. 모든 정점이 부모가 정해졌으면 트리 완성

 

손으로 작성할 땐 머릿속 알고리즘이 이렇게 돌아간다.

1부터 시작해서 1의 자식, 6의 자식, 3의 자식 ... 이렇게 연결된 노선이 끝날 때까지 계속 타고타고 들어가서끝나면 다음 분기로 넘어가는 방식은 DFS (깊이우선탐색) 알고리즘이라고 한다.

 

 

😎 DFS

루트 노드에서 시작해서 자식 노드를 한 개씩 연결하며 자식 노드가 더이상 없을 때까지 반복하며,

자식 노드가 없으면 다시 부모 노드로 돌아가 부모와 연결된 다른 자식 노드의 분기로 들어가서 깊이 있는 탐색을 반복한다.

한마디로 한 우물만 파기

출처 : 위키백과

 

dfs를 코드로 쓸 땐 '재귀 함수'를 많이 사용해서 나도 재귀 함수로 풀었다.

 

 

 

코드

---

from collections import defaultdict
import sys


n = int(input())

edges = []
for _ in range(n - 1):
    u, v = map(int, input().split())
    edges.append((u, v))


graph = defaultdict(list)
visited = [0] * (n+1)

parent_memory = 0
result_dict = {}
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)


def parent_find(node, graph, parent):
    visited[node] = 1
    result_dict[node] = parent
    for connected in graph[node]: # 연결된 노드 돌아보면서 부모 노드랑 매칭
        if not visited[connected]:
            parent_find(connected, graph, node)
            
sys.setrecursionlimit(3000)
parent_find(1, graph, 0)

for dict_ele in range(2, n+1):
    print(result_dict[dict_ele])

 

 

• graph : 각 정점과 연결되어 있는 정점을 찾아서 {'대상 정점' : ['연결된 정점']} 딕셔너리로 저장

{1: [6, 4], 6: [1, 3], 3: [6, 5], 5: [3], 4: [1, 2, 7], 2: [4], 7: [4]}

• visited : 방문한 정점 기록 리스트. 인덱스 -> 정점 숫자와 매칭. 예를 들어 4의 부모가 1로 인지가 되면 visited[4] 의 값이 1로 저장됨
• parent_find : dfs 재귀 함수!
  • node와 연결된 정점 리스트를 for문으로 돌리고, 방문하지 않았던 정점만 다시 재귀로 돌려서 모든 연결 노드가 정확힌 한 번만 방문되고 종료됨
  •  if not visited[connected]: 가 종료 조건
  • 1이 루트이므로, 1을 부모로 시작해서 자식 노드 타고 쭉쭉 내려가야 됨. parent_find(1, graph, 0) --> 1의 부모를 0으로 상정하고 재귀 함수 시작
• sys.setrecursionlimit : 재귀 깊이 제한 설정 함수. 파이썬의 기본 재귀 깊이 제한은 1000이라, 깊은 트리가 만들어지는 테스트 케이스는 안 돌아갈 수 있어서 재귀 깊이 설정하고 돌림 (재귀 쓸거면 거의 필수)

 

connected :  6 node :  1
connected :  3 node :  6
connected :  5 node :  3
connected :  4 node :  1
connected :  2 node :  4
connected :  7 node :  4

 

함수 동작 현황을 print로 찍어보면

1 -> 6 -> 3 -> 5 

1-> 4 -> 2

4 -> 7

이렇게 깊어지는 걸 볼 수 있다.

 

 

---

이전에 순열 사이클 만드는 문제에서는 재귀 함수 말고 while문으로 풀었는데,

이번 문제도 반복문으로 풀어보려니 잘 되지 않았다.

이건 숙제로 남겨두고 틈틈이 시도해봐야겠다. 아래는 반복문으로 순열 사이클 만드는 코드!

 

# 순열 사이클
# 인풋 : 테스트 케이스 t, 순열 크기 n, 순열 리스트 arr
# 순열 인덱스 저장 변수 idx, 순열 요소 저장 변수 ele, 사이클 카운트 변수 cnt, 사이클에 이미 포함된 원소 체크하는 리스트 visited 

t = int(input())

for _ in range(t):
    cnt = 0
    n = int(input())
    arr = list(map(int, input().split()))
    visited = [0] * n
    for i in range(1, n+1):
        
        idx = i
        ele = arr[idx-1]
        if visited[idx - 1] == 0:
            ele = arr[idx - 1]
            while visited[ele - 1] == 0:

                visited[ele - 1] = 1
                ele = arr[ele - 1]
                if idx == ele : 
                    cnt += 1
            

        else:
            pass
    print(cnt)