문제

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

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 하루 동안 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

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

각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 일수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 며칠 동안 발생하는지 첫째 줄에 출력한다.

아이디어

👎 연합할 수 있는 국가들을 하나의 숫자로 표현했다.

• 예제 입력 3에서

2 20 50
50 30
30 40

입력이 주어지면
chk = [[1, 1], [1, 0]] 이렇게 나타나고 0인 구역은 연합을 하지 못하는 국가이다.

• 예시

4 10 50
10 100 50 50
50 50 50 50
50 50 50 50
50 50 100 50

chk = [[1, 2, 2, 0], [1, 2, 0, 0], [0, 0, 3, 0], [0, 3, 3, 3]]

이런 방식으로 chk를 만들어서 같은 숫자끼리 더해서 나누고 arr을 변경했다.

내 코드_pypy3

:: python으로 하면 시간 초과, pypy3로 해야 통과된다.

그리고 너무 정신없고 지저분한 코드...
생각 정리를 좀 더 하고 문제를 풀어야 겠당

from collections import deque

n, l, r = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]  #반시계 방향
ans = 0
while True:
    result = {}     #{1:[120, [[0,1],[0,3],[1,2]]}이런 식으로 들어감 => 각 칸 인구의 합, 칸 인덱스
    chk = [[0] * n for x in range(n)]
    cnt = 1
    for i in range(n):
        for j in range(n):
            if chk[i][j] == 0:
                queue = deque()
                queue.append([i, j])
                s = 0   #연합 국가의 인구 수의 합
                tmp = []    #연합 국가의 인덱스 담을 배열
                while queue:
                    x, y = queue.popleft()
                    chk[x][y] = cnt
                    s += arr[x][y]
                    tmp.append([x,y])
                    for k in range(4):
                        nx = x + direction[k][0]
                        ny = y + direction[k][1]
                        if 0 <= nx < n and 0 <= ny < n:
                            if l <= abs(arr[nx][ny] - arr[x][y]) <= r and chk[nx][ny] == 0:
                                chk[nx][ny] = cnt
                                queue.append([nx, ny])
                            #다른 국가와 연합할 수 없으면 0으로 저장
                            if k == 3 and x == i and y == j and not queue:
                                chk[x][y] = 0
                                cnt -= 1
                            else:
                                chk[x][y] = cnt
                        else:
                            if k == 3 and x == i and y == j and not queue:
                                chk[x][y] = 0
                                cnt -= 1
                cnt += 1
                #result에 연합 인구 수의 총 합과 인덱스 저장
                if chk[i][j] != 0:
                    result[cnt-1] = [s]
                    result[cnt-1].append(tmp)
    if len(result) == 0:    #더이상 연합할 수 없으면 종료
        print(ans)
        break
    #연합한 국가들의 인구수를 변경함
    for i in range(1, len(result)+1):
        p = int(result[i][0]/len(result[i][1]))
        for j in range(len(result[i][1])):
            arr[result[i][1][j][0]][result[i][1][j][1]] = p
    ans += 1

[#Clone] 코드_pypy3

:: python이 아니라 pypy3로 해야 통과된다.........

from collections import deque

n, l, r = map(int, input().split())
arr = [list(map(int, input().split())) for x in range(n)]

direction = [[-1, 0], [0, -1], [1, 0], [0, 1]]  #반시계 방향
ans = 0


def bfs(start):
    global move
    queue = deque()
    queue.append(start)
    visited[start[0]][start[1]] = True
    s = arr[start[0]][start[1]]
    tmp = [start]
    while queue:
        x, y = queue.popleft()
        for k in range(4):
            nx = x + direction[k][0]
            ny = y + direction[k][1]
            if 0 <= nx < n and 0 <= ny < n:
                if l <= abs(arr[nx][ny] - arr[x][y]) <= r and not visited[nx][ny]:
                    queue.append([nx, ny])
                    visited[nx][ny] = True
                    tmp.append([nx, ny])
                    s += arr[nx][ny]
    if len(tmp) > 1:
        move = True
        for t in range(len(tmp)):
            arr[tmp[t][0]][tmp[t][1]] = int(s / len(tmp))


while True:
    visited = [[False]*n for x in range(n)]
    move = False
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                bfs([i, j])
    if move:
        ans += 1
    else:
        print(ans)
        break

클론함수 출처