알고리즘
2022. 6. 9.
[Python] 백준 2533번 - 사회망 서비스(SNS) 재귀 없이 짜기
인터넷에 돌아다니는 코드들은 전부 재귀로 돼 있어서 조금 색다르게 스택을 이용해 리프노드부터 탐색하는 코드를 올려본다. 스택을 이용하기 때문에 기본적으로 dfs방식이나 차이점은 리프노드인지 체크하여 최적화를 진행해야한다는 점이다. 리프노드부터 탐색하는 이유는 서브트리의 최적값을 갱신해 나가는 방식이기 때문이다. 이 부분을 보통 재귀로 계속 내려가다가 막다른 곳에 이를 때 최적화가 되도록 하는데 반복문으로 보이게 짜보았다. 방문하면서 연결된 길이 모두 방문한 길이어서 막다른 길이면 잎 노드로 판정하도록 변수를 하나 추가해줬다. 이렇게 막다른 길이라면 연결된 모든 길에 대해 최적화를 진행하는 방식이다. 최적화가 끝난 노드는 한 덩어리로 뭉쳐진다고 생각할 수 있다. 이때 연결된 모든 길을 체크하더라도 최적화 ..