[백준 - Python] 16234 - 인구 이동

0.  문제 링크

 

 

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

16234번: 인구 이동

---

1.  풀이 방법

 

 

(참고로 해당 방법은 python3로는 안 풀립니다..ㅠ)

해당 문제를 푸는 로직은 간단합니다.

우선 그룹(인구 이동이 가능한 좌표들)을 찾고, 인구 이동하는 것을 반복합니다.

그렇게 모든 좌표에서 이동이 끝나면, 날짜를 하루 셉니다.

 

근데.....시간 초과가 나네요ㅠ..

아마 중복으로 계산하는 부분이 있을 것으로 생각됩니다.

---

2.  코드

 

 

from collections import deque

n, l, r = map(int, input().split())
maps = [[m for m in map(int, input().split())] for _ in range(n)]
dq = deque()
new_dq = deque()
flag = True
cnt = -1
check = [[0] * n for _ in range(n)]
k = 0

while flag:
    flag = False
    for i in range(n):
        for j in range(n):
            if check[i][j] == k:
                dq.append([i, j])
                new_dq.clear()
                new_dq.append([i, j])
                sum = maps[i][j]
                check[i][j] = abs(k - 1)

                while dq:
                    y, x = dq.popleft()
                    for dy, dx in [(-1, 0), (0, 1), (1, 0), (0, -1)]:
                        if 0 <= (ny := y + dy) < n and 0 <= (nx := x + dx) < n:
                            if check[ny][nx] == abs(k - 1): continue
                            if l <= abs(maps[y][x] - maps[ny][nx]) <= r:
                                sum += maps[ny][nx]
                                dq.append([ny, nx])
                                new_dq.append([ny, nx])
                                check[ny][nx] = abs(k - 1)

                if (num := len(new_dq)) > 1:
                    avg = sum // num
                    for y, x in new_dq:
                        maps[y][x] = avg
                    flag = True

    cnt += 1
    k = abs(k - 1)
else:
    print(cnt)

---

3.  마무리

 

 

스터디때도 비슷한 로직으로 푼 친구가 있었는데 이유를 모르겠음