https://www.acmicpc.net/problem/17472구현 + MST 섬의 위치가 격자판 모양으로 주어질 때, 격자판 모양으로부터 그래프를 직접 정의하고, 그 그래프에 대해 MST를 찾으면 됩니다.이런 복잡한 문제는 어떤 것들을 구현해야 하는지 잘 나눠서 생각하면 구현하기 좋습니다.(그래도 이 문제는 구현이 엄청 복잡한 편까지는 아닙니다.) 먼저 섬부터 찾아보겠습니다.섬을 찾는다는 것은 격자판을 그대로 그래프로 보았을 때, 컴포넌트를 찾는 것과 같습니다.# 섬 찾기island_number = 2island_tiles = []for i in range(N): for j in range(M): if board[i][j] == 1: # BFS ..
https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제를 읽어보면 그냥 MST의 정의를 적은 것과 같다. 다만 다른 MST 기본 문제와 다르게 간선 정보를 직접 계산해야한다. 물론 별이 최대 100개까지라서 모든 별 사이의 간선을 다 구해놓고 시작하면 된다. 처음에는 소수점 계산하다가 문제가 생길 것 같아서 Decimal 라이브러리를 이용했는데, 혹시 몰라서 그냥 내장 float 자료형을 써보니 풀렸다. 그리고 시간차이는 내장 자료형을 쓰는 편이 ..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 오늘 백준을 들어가보니 AC Rating이 갑자기 50정도 늘어나있었다. 아무 문제도 푼게 없는데 무슨 일인가 싶다...ㅋㅋㅋ 얼떨떨한 기분으로 푼 문제, '도시분할계획'이다. 이 문제는 MST 응용문제인데, 두 MST의 합을 최소로 해야한다는 점이 조금 까다롭게 느껴졌다. 처음에는 두 MST에 속할 노드를 백트레킹이나 조합으로 골라서 매번 MST를 구해야하나..
