21738번 얼음깨기 펭귄

문제 설명

이번 문제는 얼음깨기 게임의 업그레이드 버전을 플레이하면서 펭귄을 떨어뜨리지 않고 가장 많은 얼음을 깰 수 있는 방법을 찾는 문제입니다.

얼음깨기 게임의 업그레이드버전에 추가된 규칙은 다음과 같습니다.

1. 얼음의 종류는 지지대의 역할을 하는 얼음과 일반 얼음 두 가지가 있다.
2. 일반 얼음들은 지지대가 연결되어 있어야만 깨지지 않고 있는다.
3. 펭귄이 올라가 있는 일반 얼음은 두 개의 지지대가 연결되어 있어야지만 깨지지 않는다.
4. 연결된다는 의미는 지지대로부터 서로 다른 일반 얼음들을 통해 연결 관계가 이어져 있는 것을 이야기 한다.
5. 서로 다른 지지대가 펭귄이 올라가 있는 얼음을 거치지 않고 연결되는 경우는 없다.
6. 지지대도 깨지는 얼음입니다.

 

 

문제 풀이

얼음 깨기 업그레이드 버전

아이디어

1. 펭귄을 거치지 않으면 1개의 지지대만 연결되어 있다.

위의 규칙 5번째를 살펴보면, 펭귄으로부터 연결된 각 일반 얼음들(8,10,11,14,15,16)은 펭귄을 거치지 않으면 하나의 지지대에만 연결되어 있다.

 

4번 지지대가 연결된 일반 얼음들 16, 17, 18을 살펴보면, 펭귄이 올라간 얼음을 거치지 않으면 4번 지지대 하나만 연결되어 있다.

1번 지지대가 연결된 일반 얼음들 9,10을 살펴보면, 펭귄이 올라간 얼음을 거치지 않으면 1번 지지대 하나만 연결되어 있다.

 

2. 한 연결에서 가장 많은 얼음을 깨는 방법

아이디어 1.을 통해 한 지지대에 연결된 얼음들은 펭귄이 올라간 얼음을 지나치지 않고서는 다른 지지대에 갈 수 없다는 것을 알았습니다.

 

가장 많은 얼음을 깨는 방법은, 하나의 얼음을 망치로 깼을 경우 다른 얼음이 같이 떨어지지 않는 경우입니다.

그렇게 하기 위해서는 깨지지 않은 일반 얼음이 항상 지지대에 연결되어 있도록 해야합니다.

 

한 연결에서 일반얼음이 지지대와 연결된 유형은 아래와 같습니다.

유형 1. 지지대 앞에만 일반 얼음이 있는 경우

지지대 앞에만 일반 얼음이 있는 경우

유형 2. 지지대 뒤에 일반 얼음이 있는 경우

지지대 뒤에 일반 얼음이 있는 경우

유형 3. 지지대와 다른 갈래에 일반 얼음이 있는 경우

지지대와 다른 갈래에 일반 얼음이 있는 경우

 

이와 같은 유형에서 한 얼음을 깼을 때 다른 얼음까지 떨어지지 않도록 하는 방법을 살펴보겠습니다.

1. 2번 지지대를 먼저 깬 뒤 가장 바깥쪽 얼음(13)부터 차례로 깨 나갑니다.

2. 1번 지지대 뒤쪽 일반 얼음 중 가장 바깥쪽 얼음 9번부터 1번 지지대 그 다음으로 10번, 바깥부터 안쪽으로 차례로 얼음을 깨 나갑니다.

3. 3번 지지대쪽 줄기를 바깥쪽부터 차례로 깬 뒤 다른 줄기를 바깥쪽부터 깨 나갑니다.

 

1번 2번 3번 유형에서 다른 얼음을 떨어뜨리지 않고 연결되어 있는 모든 얼음을 깰 수 있음을 알 수 있습니다.

 

3. 남겨야 하는 얼음은?

이번 문제는 최대로 깰 수 있는 얼음의 개수를 구하는 문제입니다.

이 문제를 반대로 생각하면 남겨야하는 얼음의 최소 개수를 구하는 문제이기도 합니다.

 

펭귄과 연결된 2개의 지지대를 유지하며 최소의 얼음을 남기는 방법은, 펭귄과 연결된 2개의 연결에서, 지지대와 펭귄 사이의 얼음을 최소화하는 것입니다.

연결의 유형마다 비교해야할 얼음의 개수를 확인해보겠습니다.

유형 1 : 연결된 모든 얼음의 개수

유형 2 : 지지대 뒤쪽을 제외한 지지대와 펭귄 사이의 얼음 개수

유형 3: 펭귄에서 지지대로 갈 수 있는 최소의 얼음 개수

 

이 연결 유형들 중 비교하는 얼음의 개수가 가장 작은 두 연결을 남긴다면 최대로 깰 수 있는 얼음의 개수를 구할 수 있습니다.

 

풀이

bfs

아이디어 3.을 살펴보면 각 연결 유형들은 모두 펭귄에서 지지대에 갈 수 있는 최소의 얼음 개수를 비교하도록 하고 있습니다.

 

이를 통해 bfs를 통해 펭귄에서 지지대로 갈 수 있는 최소 길이를 구한 뒤, 이 길이를 오름차순으로 정렬한 다음,

가장 작은것과, 그다음으로 작은 개수를 전체 N에서 빼주고, 마지막으로 펭귄이 올라간 얼음 1개를 마저 빼주면 답이 됩니다.

visited = [False for _ in range(N+1)]
visited[P] = True
stack = [[P,0]]

while stack:
    node,new_depth = stack.pop()
    
    if node <= S:
        info.append(new_depth)
    
    for new_node in link[node]:
        if not visited[new_node]:
            visited[new_node]=True
            stack.append([new_node,new_depth+1])

link 각 얼음이 연결된 얼음들으 가지고 있는 dict

 

 

 

해결

bfs관련 풀이로 접근했으나, visited의 사용을 잘 못한 것인지,, 맞왜틀을 많이 해서 오래걸렸던 문제입니다.

다른 분의 풀이 방식을 보니, visited를 사용하는 방법 말고 위와 같은 경우 depth를 배열로 세운 뒤, 해당 얼음의 depth를 기록하는 식으로 진행하는 방식도 생각해보면 좋을 것 같습니다.

 

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

21738번: 얼음깨기 펭귄

코드 링크 : https://github.com/beomseok37/baekjoon/blob/master/new!/21738.py