반응형
16957
-
BOJ) 체스판 위의 공알고리즘/백준 2020. 7. 11. 20:55
체스판 위의 공 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙�� www.acmicpc.net 풀이 체스판의 크기가 500x500이지만, 공들이 옮겨가면서 0인 부분이 많이 생길거라고 생각하고 DFS로 진행했다. 하지만, 6%에서 시간초과가 떴고 DFS로는 풀 수 없는 문제라고 생각이 들었다. 그래서 인접한 칸들 중 가장 작은 숫자로 이동한다는 조건을 보고, find-union을 응용하면 풀 수 있을거라고 생각했다. 일단, union부분은 필요가 없다고 생각을 했다. 생각하기도 복잡해지고, 타고 타고 이동해야하는 특성상 paren..