find-union
-
BOJ) 체스판 위의 공알고리즘/백준 2020. 7. 11. 20:55
체스판 위의 공 16957번: 체스판 위의 공 크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다. 체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙�� www.acmicpc.net 풀이 체스판의 크기가 500x500이지만, 공들이 옮겨가면서 0인 부분이 많이 생길거라고 생각하고 DFS로 진행했다. 하지만, 6%에서 시간초과가 떴고 DFS로는 풀 수 없는 문제라고 생각이 들었다. 그래서 인접한 칸들 중 가장 작은 숫자로 이동한다는 조건을 보고, find-union을 응용하면 풀 수 있을거라고 생각했다. 일단, union부분은 필요가 없다고 생각을 했다. 생각하기도 복잡해지고, 타고 타고 이동해야하는 특성상 paren..
-
BOJ) 인구 이동알고리즘/백준 2020. 7. 7. 20:28
인구 이동 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모�� www.acmicpc.net 풀이 인접해있는 땅과 인구의 차이가 주어진 L과 R 사이에 존재하면 평균을 내면서, L과 R 사이에 존재하지 않을 때 까지 묶어주는 문제다. 처음 제출하자마자 맞았지만, 효율성이 조금 떨어진다고 생각해서 코드를 수정했다. 얼마 전 포스팅했던 성곽 문제랑 푸는 방법이 비슷하다. grouping을 해주고 각 group의 평균 값을 HashMap에 저장한다. 전체 grouping이 끝나면, 각 gourp마다 평균 값을 넣어주면서 조건에 부합..