[내일배움캠프 19일차 TIL] 백준 11725 트리의 부모 찾기 with python

 

백준 11725번 트리의 부모 찾기 문제는 다음과 같다

 

문제는 간단해보이지만 이해하는데 시간이 좀 걸렸다

잠깐 문제에 대한 이해를 해보자면

 

 

첫 번째 입출력이 위와 같을 때 예제 입력에 대한 트리의 모양은 다음과 같다

이때

2번 노드의 부모는 4

3번 노드의 부모는 6

4번 노드의 부모는 1

5번 노드의 부모는 3

6번 노드의 부모는 1

7번 노드의 부모는 4

이므로 출력은 4 6 1 3 1 4가 되는 것이다.

 

---

 

1차 시도

처음 이 문제를 받고 든 생각은 트리를 만드는데 상위 노드만 저장되도록 만들면 되는 것 아닌가? 하는 생각이었다

 

{
1 : True,
2 : 4 ,
3 : 6 ,
4 : 1 ,
5 : 3 ,
6 : 1,
7 : 4
}

 

이렇게 만들어서 for 문으로 tree[i]를 출력하자! 였다

 

생각한대로 코드를 짜고 트리가 생각한대로 작동하는 것을 확인하고

 

답도 잘 나와서 제출을 했는데, 53%에서 시간초과로 실패했다

 

 

---

 

 

2차 시도

2번째는 정석대로 DFS 또는 BFS를 이용하여 푸는 것이다

그런데 트리가 힙처럼 노드들 사이에 대소 관계가 있는 것이 아닌데 어떻게 해야하는지에 대한 고민이 많이 들었다

그래서 리스트를 하나 더 생성해서 리스트의 인덱스를 노드 번호에 부모 노드의 값을 넣어야겠다는 생각을 했다

 

이렇게 초기화되어있는 배열에서

 

 

이렇게 만들어서 1번부터 출력해야겠다는 생각이 들었다

 

원래 dfs함수는 

# 깊이 우선 탐색
def dfs(tree, n, visited):
    visited.append(n) # n을 방문한 노드에 추가
    for t in tree[n]: # 현재 노드에서 이어진 노드들 돌면서
        dfs(tree, t, visited) # 다음 노드 탐색
    return visited

 

이렇게 방문한 노드 순서대로 출력되는데

이렇게 작성하면 visited에는 [1,6,3,5,4,2,7]이 출력되게 된다

 

하지만 문제에서는 부모 노드의 값을 출력해야하기 때문에 dfs 함수를 다음과 같이 바꾸어주었다

# 깊이 우선 탐색
def dfs(tree, n, parent):
    for t in tree[n]: # 현재 노드에서 이어진 노드들 돌면서
        if parent[t-1] == 0: # 부모노드가 정해지지 않았다면
            parent[t-1] = n # 현재 노드를 부모 노드로 설정
            dfs(tree, t, parent) # 다음 노드 탐색
    return parent

 

트리는 원래의 트리를 만드는 것처럼 인접 노드들을 value로 가지는 딕셔너리로 만들어 주고

정답을 출력해보았다

 

 

1번노드는 부모노드가 없지만 4를 방문하게 되면서 부모 노드에 4가 들어가버리게 된 것 같다.

하지만 1번노드의 부모는 출력하지 않아도 되기 때문에 오류없이 잘 작동하는 것을 확인하고 제출했다!

 

 

 

수많은 시도끝에 통과...ㅠㅠㅠㅠ

 

전체 코드는 여기서!

 

 

---

코드도 그렇게 길지 않고 작동하는 원리도 머리로는 이해되지만 막상 코드를 작성하려니 너무 어려웠다...

그리고 재귀로 푸는 경우 최대 횟수가 1000으로 제한되어있어  제한을 늘려주어야 한다

따라서 재귀 말고 스택을 이용해서 푸는 DFS도 연습해봐야겠다!

문제 푸는데 시간이 오래 걸리지만,,, 그래도 풀었다는 것에 희망을 가지고 열심히 해야지.,...

 

문제 하나에 너덜너덜해져버린 나,,,