![[백준] 인구이동 16234 C++](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FRy4SZ%2FbtsNB5NO2Hd%2FIVLimLhSfKKo3kb5CmHnk0%2Fimg.png)
알고리즘/백준2025. 4. 29. 10:45[백준] 인구이동 16234 C++
https://www.acmicpc.net/problem/16234 해설인구이동 문제이다.핵심은 인접한 마을의 인구수가 L보다 크거나 같고 R보다 작거나 같으면 이동이 가능하다고 판단하고 인구이동을 시키는것이다. Connected Component를 구하는 문제이다. 이동이 가능하다는 것의 판단은 인접한 두 마을 사이의 인구차이 값에 절대값을 취해서 판단해주면 된다.문제는 n*n짜리 보드(배열)에서 '어떻게' 이동이 가능한 마을을 '묶어서' 처리하냐는 것이다. 본인 처음에 dfs나 bfs로 탐색하여 unoin find?나 그룹화할 또 다른 배열을 만들어서 같은 번호의 그룹끼리 합을 더하고 평균을 내서 원본 board배열에 값을 갱신하는 아이디어를 생각했는데 이 보다 간단한 방법이 있다. '묶어서' 처리한..