23.06.04 - 23.06.10 공부 (그래프 파트 3 : MST)
이번 그래프 파트는 '최소 신장(스패닝) 트리'라 불리는 MST이다. 바킹독 MST 문제집은 다 풀어놓은 상태라 라이 블로그 추천 문제집을 활용하였다.
https://www.acmicpc.net/workbook/view/5057
문제 수가 그렇게 많지 않은데 공부 기간이 저렇게 길게 적혀있는 이유는.. 9373번 덕분이다. 나머지 문제는 하루만에 다 풀었는데, 9373번은 없는 시간 쪼개가며 고민하다보니 조금 오래 걸렸다. (사실 그마저도 풀어내지 못해서 해설을 봤다 ㅠ)
1. 백준 1922번 - 네트워크 연결
https://www.acmicpc.net/problem/1922
1922번: 네트워크 연결
이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.
www.acmicpc.net
기본문제. 프림이든, 크루스칼이든 MST를 그대로 구현하면 된다.
2. 백준 6497번 - 전력난 (원. Dark Roads)
https://www.acmicpc.net/problem/6497
6497번: 전력난
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들
www.acmicpc.net
이것도 기본문제. 다만 MST를 구성한 뒤 그 최종값을 출력하는 것이 아니라, 처음에 전체 돈을 구해놓은 뒤, MST의 최종값을 뺀 값을 출력해야 한다.
3. 백준 1944번 - 복제 로봇
https://www.acmicpc.net/problem/1944
1944번: 복제 로봇
첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어
www.acmicpc.net
재밌는 문제. '복제'라는 것 때문에 어려워질 수 있는데, 풀이 논리는 28119번과 비슷하게 흘러간다.
로봇의 처음 위치와 각 열쇠 위치를 정점으로 잡고 각 정점 간 거리를 모두 구해놓는다. 이는 bfs로 빠르게 해결할 수 있다.
각 정점들을 MST로 연결한 것이 답이 되는데, 281복제 시점을 28119번에서의 순간이동 시점과 연결지어 생각해보면 쉽게 이해가 된다. 어떤 정점에서 MST를 더 뻗어나갈 수 없을 때, 처음 정점에서 복제시켜둔 로봇을 출발시키는 것은 28119번에서 순간이동을 통해 처음 지점으로 돌아와 다시 탐색하는 것과 같다고 볼 수 있다. 따라서 bfs로 구해둔 정점 간 거리로 MST를 구성하여 문제를 해결할 수 있다.
4. 백준 4343번 - Arctic Network
https://www.acmicpc.net/problem/4343
4343번: Arctic Network
The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost
www.acmicpc.net
아무리 읽어도 구하고자 하는 것이 잘 이해가 안 됐던 문제.. 질문 게시판의 도움을 받아 겨우 문제 풀이를 시작했다.
인공위성이 있는 인접 행성끼리는 $D$에 상관없이 통신할 수 있고, 그렇지 않은 경우에는 $D$ 이하의 거리를 가진 경우에만 라디오로 통신할 수 있다. 예제는 1번 행성과 4번 행성에 인공위성을 두거나, 2번 행성과 3번 행성에 인공위성을 두었을 때, 최소의 $D$값으로 모든 행성이 통신할 수 있다.
라디오로 묶인 어떤 행성 집단의 행성 개수를 $a$개라고 하자. 그 $a$개 중 하나의 행성에만 인공위성을 설치하면 그 행성 집단은 다른 집단과도 통신이 가능하다. 인공위성을 설치할 행성은 이 다음에 다른 행성과 라디오 간선을 이을 필요가 없다. 따라서 크루스칼 알고리즘으로 거리가 낮은 순으로 행성들을 이은 다음, 이어진 간선의 개수가 $P-S$개 일 때의 거리를 출력하고 종료하면 된다.
5. 백준 9373번 - 복도 뚫기 (원. Getting Through)
https://www.acmicpc.net/problem/9373
9373번: 복도 뚫기
각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약
www.acmicpc.net
알고리즘 분류를 알고 풀 때의 가장 무서운 문제는 '이 알고리즘 태그가 왜 달렸는지 모르겠는 문제'다. 이 문제도 처음에는 MST를 도대체 어디에 써야할 지를 몰라 많은 고민을 했었다.
<사풀이>
그래서 처음엔 MST 생각은 잠시 접어두고, 어떤 식으로 풀 수 있을지를 고민했다. 어떤 센서 하나 가 복도에 있을 때, 그 센서를 지나가는 방법은 두 가지가 있다.
- 왼쪽 벽과 센서 사이 (이하 L방향)
- 오른쪽 벽과 센서 사이 (이하 R방향)
이에 따라, 센서 두 개를 지나가는 방법은 네 가지로 나눠볼 수 있다.
- L방향 -> L방향
- L방향 -> 두 센서 사이 -> R방향
- R방향 -> 두 센서 사이 -> L방향
- R방향 -> R방향
따라서 각 센서당 2개의 노드를 할당해 L방향과 R방향 거리를 저장할 수 있도록 한 다음, y방향으로 정렬, 그 후 위에서부터 아래로 순차적으로 내려오면서 센서들을 지나가는 4가지 방법을 각각 우선순위 큐에 넣어 크루스칼 알고리즘을 진행하도록 했다.(이때 우선순위 큐는 최대 힙이다.) 진행하면서 가장 마지막 노드들이 첫 번재 노드들과 같은 집합에 속하게 될 때 바로 종료한다.
<정해>
사실 완벽하게 틀린 풀이이다. 센서 위치가 정말로 예쁘게 주어지지 않는 한, 위와 같은 풀이는 불가능함을 알 수 있다. 당장 센서 여러 개의 y축 위치가 동일한 경우만 생각해도 그렇다.
센서 뿐만 아니라 두 벽 또한 정점으로 설정한 뒤, 모든 정점 간 거리를 계산한다. 원래의 크루스칼 알고리즘에 맞추어 우선순위 큐를 최소 힙으로 잡았을 때, 복도를 지나갈 수 있냐 없냐가 결정되는 때는 두 벽이 서로 같은 집합에 속할 때임을 알 수 있다. 그 전까지 이어지는 간선들은 L방향끼리만의 간선, R방향끼리만의 간선이므로 이것만으로는 복도를 지나갈 수 있는지 없는지를 알 수 없다.
센서를 정점으로 잡는 것까지는 좋았는데, 벽을 정점으로 볼 생각을 하지 못하고 풀이 방향도 완전 반대로 생각한 것이 아쉬웠다. 대회에서 이런 문제를 마주쳤을 때, MST를 바로 떠올릴 수 있을지가 의문이다. 실전에서는 case work의 늪에 빠질 것만 같은 문제. 그만큼 많이 배워간 문제이다.