목록코테 #python #14675 #BOJ #단절점과단절선 #백준 #코딩테스트 (1)

평범한 필기장

[BOJ_Python] 14675_단절점과 단절선

이 문제를 보고 단절선을 찾는 함수 단절점을 찾는 함수를 각각 만들어보려 했는데 도저히 생각이 나지 않았다. 그렇게 문제를 켜두고 생각을 해보니 트리에서 어떤 간선을 없애도 항상 2개의 트리로 나눠진다는 것을 떠올렸고 트리의 끝점 즉, 자식이 없는 노드를 제외하고 나머지 노드를 제거하면 트리는 2개의 트리로 항상 나눠 진다는 것을 생각해냈다. 그래서 처음에 graph를 만들 때 빈 리스트가 (노드의 개수 + 1) 개인 2차원 빈 리스트를 만들고 각 리스트에 연결된 노드를 넣었다. (1번 노드와 3번 노드가 연결되어 있으면 1번째 리스트에 3을 넣고 3번째 리스트에 1을 넣는 방식) 그리고 간선을 없앤다고 하면 항상 yes를 출력하게 하고 노드를 없애면 그 노드가 자식이 없는 마지막 노드인지를 확인하고 마..
코딩 테스트 준비/BOJ 2023. 3. 9. 12:52
이전 Prev 1 Next 다음