Union-Find
-
[백준 3108 - JAVA] 로고Algorithm 2020. 11. 9. 18:28
3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net N개의 직사각형을 그리는 필요한 PU명령의 최솟값을 출력한다! 이삭이가 BFS를 이용해서 컬러링을 해보려했다는 것에서 아이디어를 얻어 풀었던 문제다. 일반적인 BFS로 풀경우 하나의 직사각형안에 겹치지 않게 딱맞게 직사각형이 들어갈 경우 겹친다고 체크하는 문제가 발생한다. 나는 직사각형을 그리면서 겹칠 경우 FindSet을 이용해 집합을 확인하고, 같은 집합이 아닐 경우 ans에서 1을 빼주도록 구현했다. 가운데 영점이 존재하는 좌표계이기 때문에 500을 더해서 배열에 저장..