목록백준 11725번 (1)

Tori의 개발 공부

[python] 11725번 - 트리의 부모 찾기

문제 파이썬 풀이 트리를 그래프를 저장하듯 리스트 형태로 저장하고, 부모 노드를 저장하는 리스트를 생성하는 것이 포인트였다. 부모 노드를 저장하는 리스트는 리스트의 인덱스가 해당 노드가 되고 저장된 값은 부모 노드가 된다. 예를 들어보면 2와 연결되어있는 노드 들은 2의 부모 노드와 자식 노드로 나뉜다. 이때 부모 노드를 저장하는 리스트에서 2의 부모 노드가 무엇인지 가져와 2와 인접한 노드들 중 부모 노드를 제외한다. 그럼 나머지는 전부 2의 자식노드가 된다. 이제 자식 노드로 구별된 노드들의 부모 노드를 2로 저장한다. 이와 같은 과정을 모든 노드들에 접근하면서 부모 노드를 저장한다. 모든 노드들을 접근하는 과정에서는 dfs나 bfs를 이용하여 전체 탐색한다. 나는 dfs를 통해 구현하였다. from..
Algorithm/백준 문제풀이 2021. 12. 20. 18:04
이전 Prev 1 Next 다음