# [이.취.코] [백준] Chap 13. BFS_DFS - Q21. 인구 이동

- Author: @mildsalmon
- Published: 2021-09-28
- Updated: 2021-09-28
- Source: http://blex.me/@mildsalmon/%EC%9D%B4%EC%B7%A8%EC%BD%94-%EB%B0%B1%EC%A4%80-chap-13-bfs_dfs-q21-%EC%9D%B8%EA%B5%AC-%EC%9D%B4%EB%8F%99
- Tags: 파이썬, 알고리즘, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, bfs, 백준, 인

---

# 1. 인구 이동

- 난이도
	- 중
- 풀이 시간
	- 40분
- 시간 제한
	- 2초
- 메모리 제한
	- 512 MB
- 출처
	- [16234번: 인구 이동 (acmicpc.net)](https://www.acmicpc.net/problem/16234)

### A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

### B. 내 답안

##### a. 1차 시도 (실패)

```python

from collections import deque

N, L, R = list(map(int, input().split()))

graph = []
# diff_graph = [[0] * 4 for _ in range(N)]
diff_graph = []

for i in range(N):
    graph.append(list(map(int, input().split())))

ds = ((-1, 0), (0, 1), (1, 0), (0, -1))

q = deque()
# 좌표, 시간
q.append([0, 0])

while True:
    time = 0
    answer = [[0] * N for _ in range(N)]
    while q:
        x, y = q.popleft()

        for d_i in range(len(ds)):
            dx = x + ds[d_i][0]
            dy = y + ds[d_i][1]

            if 0 <= dx < N and 0 <= dy < N:
                value = abs(graph[x][y] - graph[dx][dy])
                if L <= value <= R:
                    q.append([dx, dy])
                    answer[dx][dy] += 1
                else:
                    continue
            else:
                continue
    total_pop = 0
    total_count = 0

    for i in range(N):
        for j in range(N):
            if answer[i][j] > 0:
                total_pop += graph[i][j]
                total_count += 1

    if total_count == 0:
        break

    for i in range(N):
        for j in range(N):
            if answer[i][j] > 0:
                graph[i][j] = (total_pop // total_count)

    time += 1

print(time)

# print(diff_graph)

    # for i in range(N):
    #     for j in range(N):
    #         diff_list = [0] * 4
    #         for d_i in range(len(ds)):
    #             dx = i + ds[d_i][0]
    #             dy = j + ds[d_i][1]
    #
    #             if 0 <= dx < N and 0 <= dy < N:
    #                 value = abs(graph[i][j] - graph[dx][dy])
    #                 diff_list[d_i] = value
    #             else:
    #                 diff_list[d_i] = 0
    #         diff_graph.append(diff_list)

```

##### b. 2차 시도 ()

##### c. 회고

> 내 풀이

- 무한루프 안에 bfs를 구현하였다.

> 반성

-  이미 방문한 땅(국경선이 열린 땅)에 대한 체크를 어떻게 해야할지 감이 안왔다.
-  중첩 반복문 안에 다시 중첩 반복문을 만들어서 시간초과도 발생했다.
	-  단순하게 중첩 반복문을 사용하기보다, 가능하다면 앞 부분에서 작성한 코드를 활용하는 방법을 생각해봐야겠다.

### C. 문제 해설

> 이해한 내용을 바탕으로 작성했습니다.

예제 4번과 5번에 대한 풀이는 다음과 같다.

![](https://static.blex.me/images/content/2021/9/28/11_3ChBObo3JHBuJUTZhWVN.jpg)

![](https://static.blex.me/images/content/2021/9/28/11_jBL7T3mYwfTAfYcEqsnp.jpg)

1. 모든 땅에 방문한다.
	- 연산의 반복을 방지하기 위해 방문한 땅은 체크한다.
2. 4방향(상하좌우)를 확인하고 조건(두 나라의 인구 차이가 L명 이상, R명 이하)을 만족하면 조건을 만족하지 않을때까지 bfs를 반복한다.
	- 방문한 땅으로 체크한다.
	- 확인한 땅을 bfs q에 집어넣는다.
3. bfs q가 끝나면(조건을 만족하는 나라끼리 국경선을 다 열었으면) 인구 이동을 시작한다.
4. 1번으로 돌아가서 모든 땅을 방문할 때까지(방문한 땅이 전부 체크될 때까지)반복한다.

---

bfs쪽에서 인구이동할 도시를 2중 for문으로 찾으면 시간초과가 발생한다.

```python

for i in range(N):
	for j in range(N):
		if check[i][j] == group_num:
			graph[i][j] = result // go_count

```

[33773569번 소스 코드 (acmicpc.net)](https://www.acmicpc.net/source/33773569)

##### a. 책 답안

[python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/13/7.py)

# 참고문헌

[1] 나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

[2] [16234번: 인구 이동 (acmicpc.net)](https://www.acmicpc.net/problem/16234). Baekjoon. (accessed Sep 28, 2021)