Baekjoon 16234 인구 이동 JAVA

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%2016234

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 map가 주어졌을 때 이웃나라에 대해서 인구수 차이가 L 명 이상 R 명 이하면

연합으로 연결하고 연결한 모든 연합을 총인구수의 평균값으로 갱신해 준다.

​

모든 나라를 체크하면 하루가 지나게 되고 총 며칠이 동안

인구수를 조정할 수 있는지 구하는 문제다.

​

해당 문제는 bfs를 이용했고, 처음에 입력 처리를 한 뒤 무한 루프를 돌면서

1. 방문하지 않은 나라면 리스트에 넣고 bfs 진행

​

2. dfs에서는 인구수를 더해주고, 이동 가능하면(차이가 범위 안에 들어오고, 범위 안 벗어나고, 방문 안 했으면)

리스트에 추가하고, dfs를 호출해 준다.

​

3. 2번 동작이 끝나면 리스트 크기를 비교하는데 만약 1보다 크다면(방문 안 한 곳을 처음에 넣어주기 때문에)

인구수 조정을 해주고, 인구 수 조정을 했는지 나타내는 변수를 ture로 변경시켜준다.

​

4. 위의 동작이 끝나면 인구 수 조정 확인 변수를 체크해 조정이 있다면 하루 증가시키고 없다면 무한 루프를

종료하고 결괏값을 출력한다.