[BOJ16234] 인구 이동

문제

• NxN 크기 땅. 1x1칸엔 각 나라 존재
• 인접한 나라 국경선 존재
• 인구이동 조건
  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
  • 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
  • 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
  • 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
  • 연합을 해체하고, 모든 국경선을 닫는다.
• 각 나라 인구수 주어질 때, 인구이동 몇 번

입력

• 첫째 줄 n(1<= <=50), l, r(1<= <=100)
• 둘째 줄부터 각 나라 인구수

출력

• 인구 이동이 몇 번 발생하는지 출력

설계

• 그래프를 탐색하는 방식은 BFS 선정
• 1,1 부터 n,n까지 전부 탐색하며, 인접한 칸이 l이상 r이하의 조건인 경우만 하나의 클러스터로 두고 평균 값 업데이트
• Days 변수로 하루씩 체크하고, 변경이 없는 (인구 이동 없는) 날 이전까지 이동한 날짜 출력

피드백

• 실수로 다음 노드 변수를 지정할 때 cx + dy[i] 적용해서 계속 틀림
• 고쳐도 시간초과 (시간복잡도 고려 못 함) —> BFS로 클러스터를 확인했으면, 탐색 종료 후 바로 평균 값 업데이트

How I solved(click to github)

---

ref :
BOJ16234