[Python] 백준 2533 사회망 서비스(SNS)

문제 링크 : https://www.acmicpc.net/problem/2533

2533번: 사회망 서비스(SNS)

 

1. 접근 방법

DP와 DFS를 고민했는데, 나는 둘 다 사용한 방법으로 가닥을 잡았다.

문제를 해결하고 DP로만 해결하는 등의 풀이도 고민했지만, 잘 되지는 않아 시간은 조금 오래 걸렸지만, 해결했다.

 

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/2000/2500/2533.py

GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다.

📕코드 해설

DFS를 활용하여 리프노드까지 간 후 리프 노드에서 올라오며 계산을 했지만, 그림에서는 편의상 리프 노드에서 바로 시작하는 것으로 구현했다. 그리고 각 DP의 위쪽 칸은 해당 노드가 얼리 아답터일 때, 밑의 칸은 아닐 때로 계산했다.

처음 리프노드들은 얼리 아답터가 아닌 경우는 따로 계산할 수 없으므로, 얼리 아답터일 때, 1명씩 기록한다.

DFS로는 5, 6번 점을 확인한 후 2번 점을, 7, 8번 점을 확인한 수 4번 점을 확인하지만, 편의상 동시에 확인하면 다음과 같다. 만약 얼리 아답터라면, 자식 노드가 얼리 아답터인지와 상관없이, 이전까지의 최소 경우의 수를 더한다.

만약 얼리 아답터가 아닌 경우라면, 자식노드들이 얼리 아답터인 경우가 되어야 하므로, 해당 경우의 수를 더한다.

마지막으로, 1을 루트로 정하여 계산하였다.

만약 1이 얼리 아답터라면, 2, 3, 4번 점의 각각의 최소 경우의 수를 구하면 되므로 1 + (1 + 0 + 1) = 3,

만약 1이 얼리 아답터가 아니라면 자식이 모두 얼리 아답터인 경우 1 + 1 + 1 = 3이 된다.

 

마지막으로, 1번점의 최소 경우의 수를 출력한다.

 

3. 생각 정리

더 간단한 풀이가 가능했을 것 같지만, 사실은 조금 귀찮아서 더 이상의 구현을 하지는 않았다.

만약 더 빠르게 한다면, 위의 풀이 설명 과정을 stack이나 queue를 활용하여 빠르게 해결할 수 있을 것 같다.