[백준] 21738번: 얼음깨기 펭귄 문제 풀이 파이썬

문제

도도는 심심해서 보드게임 카페에 갔다. 마침 평소에 즐겨 했던 얼음 깨기 펭귄의 업그레이드 버전으로 특수 얼음 깨기 펭귄 보드게임이 나와 직접 플레이해 보기로 결정했다. 특수 얼음 깨기 펭귄 게임은 특수 안경이 있어 특수 안경을 끼고 얼음들을 보면 얼음들 간의 연결 관계가 보인다.

특수 얼음 깨기 펭귄 게임에 있는 얼음의 종류로는 지지대의 역할을 하는 얼음과 일반 얼음 총 2가지의 얼음이 존재한다. 지지대의 역할을 하는 얼음의 경우, 빨간색으로 구분

하여 볼 수 있으며 일반 얼음을 지탱해 주어 일반 얼음들이 깨지지 않도록 도와준다. 일반 얼음의 경우에는 1개의 지지대만이 연결되어 있어도 얼음이 깨지지 않지만 펭귄이 올라가 있는 얼음은 2개 이상의 지지대의 역할을 하는 얼음이 연결되어 있어야만 얼음이 깨지지 않는다. 이때, 지지대가 연결되어 있다는 것은 지지대로부터 서로 다른 일반 얼음들을 통해 연결 관계가 이어져 있는 것을 이야기한다. 특수 얼음 깨기 펭귄 게임에서 도도가 펭귄을 떨어뜨리지 않고 최대 몇 개의 얼음을 깰 수 있을까?

입력

첫째 줄에 얼음 블록의 개수 $N($ 3 <= N <= 328,000 )과 지지대의 역할을 하게 되는 얼음의 개수 $S($ 2 <= S <= N-1 ), 펭귄이 위치한 얼음 블록의 번호 $P$( S <= P <= N ) 가 주어진다. 지지대의 역할을 하게 되는 얼음의 개수가 $S$일 때, $1$번부터 $S$번까지의 얼음은 지지대의 역할을 한다.

둘째 줄부터 $N-1$개의 줄에 두 개의 정수 $A$, $B$가 주어진다. 이는 $A$번 얼음과 $B$번 얼음이 연결되어 있음을 의미하며 같은 연결은 여러 번 주어지지 않는다.

게임 시작 시 펭귄은 일반 얼음 위에 위치해 있고 어떤 얼음도 깨지지 않은 상태로 시작하게 된다. 각 얼음들은 $1$번부터 $N$번까지 정수 번호로 주어져 있으며 서로 다른 두 얼음을 잇는 경로는 하나뿐이다. 더불어 서로 다른 지지대가 펭귄이 올라가 있는 얼음을 거치지 않고 연결되어 있는 경우는 없다.

출력

플레이어가 펭귄을 떨어트리지 않고 깰 수 있는 얼음의 최대 개수를 구하여라. 지지대의 역할을 하는 얼음 역시 깰 수 있는 얼음에 속한다.

첫번째 접근

• 펭귄이 서 있는 얼음과 연결된 6개의 얼음을 각각 탐색한다.
• 6개의 얼음에서 기둥 얼음까지의 갯수를 구한다.
• 6개의 얼음 중에 갯수가 가장 적은 두 얼음의 갯수 합만 제외하고 모든 얼음을 깬다.

두번째 접근

• 기둥 얼음을 하나씩 탐색하여 펭귄이 있는 위치까지 갯수를 카운트 한다.
• 갯수가 가장 작은 2개를 전체 얼음에서 제외한다.
• 펭귄이 서 있는 얼음까지 고려해야하기에 1을 추가로 제외한다.

전체 코드

import sys

input = sys.stdin.readline
# 재귀함수 횟수 제한을 늘려줌
sys.setrecursionlimit(999999)

N, S, P = map(int, input().split())
graph = [[] for i in range(N + 1)]

# 각각 얼음이 연결된 관계를 그래프로 저장
for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

iceBroken = []
# 방문한 얼음
visited = [0] * (N+1)


def dfs(n, cnt):
    # 현재 방문한 얼음이 펭귄이 서있는 곳이면
    # 해당 기둥의 연결 얼음 갯수 반환
    if n == P:
        iceBroken.append(cnt)
        return
    visited[n] = 1
    for i in graph[n]:
        # 해당 얼음과 연결된 얼음 탐색
        if not visited[i]:
            dfs(i, cnt + 1)

# 6개의 얼음 기둥 탐색
for i in range(1, S+1):
    dfs(i, 0)

iceBroken.sort()

# 전체 얼음 - 가장 연결갯수가 적은 기둥 2개 - 펭귄이 서있는 얼음
print(N - iceBroken[0] - iceBroken[1] - 1)

재귀함수를 사용하지 않고 큐만 사용해서 탐색을 했을 때, 답은 맞았으나 시간초과 이슈를 해결할 수 없었다. 재귀함수가 더 연산시간이 많이 소요될 것이라 생각했는데 꼭 그런것 만은 아니었나보다...