https://www.acmicpc.net/problem/17472 [17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net](https://www.acmicpc.net/problem/17472) 섬 구분하기 일단은 각 섬을 구분하기 위해 init_land 함수를 구현했다. 섬을 구분하도록 하는 변수 group을 2로 두고, BFS로 근처 땅을 모두 group으로 초기화하도록 했다. 섬 하나에 속한 땅을 모두 group으로 바꾼 후에는 1 증가하고 다음 땅을 찾는다. 즉, init_land 이후 ..
union-find
https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net BFS (2056ms) 각 간선을 List로 저장하고 Query가 주어질 때마다 간선 리스트를 바탕으로 BFS로 갈 수 있는 노드를 찾도록 했다. 단순한 방법으로 통과하기는 했지만 시간이 2056ms나 나왔다. N개의 노드에 N - 1개의 간선이 있고, 모든 노드가 이어져 있다는 조건으로, 사이클이 없는 트리 구조라는 것을 활용해보고 싶었지만 떠..
