트리2 [python] 11725번 - 트리의 부모 찾기 문제 파이썬 풀이 트리를 그래프를 저장하듯 리스트 형태로 저장하고, 부모 노드를 저장하는 리스트를 생성하는 것이 포인트였다. 부모 노드를 저장하는 리스트는 리스트의 인덱스가 해당 노드가 되고 저장된 값은 부모 노드가 된다. 예를 들어보면 2와 연결되어있는 노드 들은 2의 부모 노드와 자식 노드로 나뉜다. 이때 부모 노드를 저장하는 리스트에서 2의 부모 노드가 무엇인지 가져와 2와 인접한 노드들 중 부모 노드를 제외한다. 그럼 나머지는 전부 2의 자식노드가 된다. 이제 자식 노드로 구별된 노드들의 부모 노드를 2로 저장한다. 이와 같은 과정을 모든 노드들에 접근하면서 부모 노드를 저장한다. 모든 노드들을 접근하는 과정에서는 dfs나 bfs를 이용하여 전체 탐색한다. 나는 dfs를 통해 구현하였다. from.. 2021. 12. 20. 트리와 그래프 내용 정리 트리와 그래프 그래프란? 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. 그래프의 종류 무방향 그래프 간선에 방향이 존재하지 않아 양방향으로 이동이 가능하다. (A,B), (B,A)는 동일한 간선이다 방향 그래프 간선에 방향이 존재하는 그래프로 지정된 방향으로만 이동이 가능하다. A->B로 가는 간선은 로 표시하며 와는 다른 간선이다. 가중치 그래프 간선에 비용이나 가중치가 할당된 그래프이다. 완전 그래프 한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프 단순 그래프 두 정점 사이의 연결선이 최대 한 개인 그래프 부분 그래프 원래의 그래프에서 일부 정점이나 간선을 제거해 만든 그래프 그래프 구현 방.. 2021. 12. 5. 이전 1 다음
