[BOJ] 16234번 인구 이동 (C++)

문제 (https://www.acmicpc.net/problem/16234)

16234번: 인구 이동

DFS로 해결한 문제!

처음엔 문제를 제대로 이해하지 못하고 너무 어렵게 접근해서 삽질했다 ㅠㅠㅠㅠ

하지만.. 정신 차리고 풀어보니 간단했다.....😑

예제가 5개 있는데 예제 4, 예제 5를 직접 구해보면 이해가 잘 된다!

 

dfs를 진행하며 국경선이 열리는 곳의 좌표들을 v(vector)에 넣어준다.

- v의 size가 1이면? 해당 좌표에서는 국경선이 열리는 곳이 없는 것

- 아니면? 1. dfs를 돌며 구한 인구의 합으로 새로운 인구수를 구한다. 2. (v에 들어있는 좌표들, 변경할 값)을 record(vector)에 넣어준다.

 

가능한 dfs를 모두 진행 후 -> record에 있는 값들로 값을 변경해줌

 

while문 탈출 조건 (더 이상 인구 이동이 없는 경우)

- v의 size가 1일 때마다 증가시켜준 cnt 변수 값이 n * n과 같을 때

 

출력값

- while문을 한 번 돌 때마다 증가시킨 변수 값

---

[소스코드]

---

2021-11-10

Gold 5

알고리즘 분류

- 구현

- 그래프 이론

- 그래프 탐색

- 너비 우선 탐색

- 시뮬레이션