백준 알고리즘 2655 - 가장 높은 탑 쌓기

https://www.acmicpc.net/problem/2655

2655번: 가장높은탑쌓기

문제는 백준 알고리즘 사이트에서 확인하세요~

 

오늘 다룰 문제는 조금 복잡합니다.

 

문제가 원하는 답은 '가장 높게 쌓은 탑'에 사용된 벽돌의 개수와 사용된 벽돌의 번호를 나열하는 것입니다!

 

복잡한 문제인 만큼 조건이 까다롭네요. 그 중에서 중요한 조건 몇가지를 추렸습니다.

 

1. 밑면이 좁은 벽돌 위에 밑면이 넓은 벽돌은 놓을 수 없다.

2. 무게가 무거운 벽돌을 무게가 가벼운 벽돌 위에 놓을 수 없다.

 

인풋 데이터로 밑면, 높이, 무게가 주어진다는 점도 확인하고요~

 

이 문제는 Bellman-Ford를 이용하면 해결할 수 있습니다.

 

진행순서를 잘 파악해보면, 아무것도 없는 상태에서 벽돌을 올리는게 시작상태이고

 

쌓을 수 있는 벽돌이 없을때 종료상태가 됩니다.

 

n개의 벽돌을 전부 쌓는것이 아니기 때문에 그냥 DP로는 해결하기 힘든 문제입니다.

 

하지만 Bellman Ford도 DP에 일종이라는 점!

 

그럼먼저 인접리스트를 만들어 볼까요?

 

1번 조건과 2번 조건으로 다음과 같은 식을 떠올릴 수 있겠네요!

if 밑면 1 > 밑면2 & 무게 1 > 무게2 then 벽돌 1위에 벽돌 2를 놓을 수 있다.

위 식으로 높이와 관련된 인접리스트를 만들 수 있습니다.

문제 예시를 그래프로 표현했습니다.

 

이제 이 그래프를 Bellman Ford로 DP하면 답이 나올까요?

 

재밌는 것은 방문하는 정점의 순서에 따라 블록의 최대 높이와 블록을 쌓는 순서가 바뀝니다.

 

먼저 방문하는 순서를 Bellman Ford를 사용할 수 있도록 바꿔주어야합니다.

 

그래프의 방문순서를 정하는데는 위상정렬(Topological Sort)을 사용하겠습니다.

 

위상정렬을 할때 DFS을 사용하면 좀 더 손쉽게 구현을 할 수 있습니다.

 

벽돌 번호에 따라 DFS하면 [0-4-2-1-3-5] 이렇게 나오네요.

 

[0-4-2-1-3-5] 순으로 DP를 세워 Bellman Ford를 수행하면 해결되는 문제였습니다.

 

그럼 다음에 만나요~