(22 복습) 삼성 SW 역량 테스트 기출 문제 / 백준 / 16234번: 인구이동

[sallyy1]

• 턴마다 시행되는 문제
• 처음에 턴(while True 문) 밖에서 해당 턴에서 사용할 임시 자료구조를 선언하는 실수를 했었음

# 1. 국경선 공유
# 2. 인구 이동 수행
# 3. 연합 해체 및 국경선 닫기


from collections import deque


answer = 0 # 인구이동이 발생하는 일자 수

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


dx = [-1,1,0,0]
dy = [0,0,-1,1]





# 인구이동이 발생하지 않을 때까지 게임 반복
while True:
    idx = -1 # 연합(Group)의 인덱스 번호
    ok = False ###

    # (주의) 여기서 자료구조 리셋해줘야 함
    check = [[-1] * n for _ in range(n)]
    q = deque()

    # 정보 임시 저장할 자료구조
    after_num = []  ## 각 연합 당 인구수
    after_xy = []  ## 각 연합 당 위치 리스트



    for i in range(n):
        for j in range(n):
            if check[i][j] == -1:
                q.append((i, j))
                ###print((i, j))

                idx += 1
                check[i][j] = idx ## (주의) 큐 시작 위치도 그룹 번호 매겨주기

                #  정보 임시 저장할 자료구조
                temp = [] ## 해당 연합에서 방문하는 위치 리스트
                temp.append((i, j))

                num_sum = a[i][j] ## 해당 연합의 총 인구수


                while q:
                    x, y = q.popleft()

                    for k in range(4):
                        nx, ny = x+dx[k], y+dy[k]

                        if 0<=nx<n and 0<=ny<n:
                            res = abs(a[nx][ny] - a[x][y])

                            if check[nx][ny] == -1 and l <= res and res <= r:
                                ###print((nx, ny))
                                check[nx][ny] = idx
                                q.append((nx, ny))

                                temp.append((nx, ny)) ##
                                num_sum += a[nx][ny] ##

                                ok = True ###

                # 연합 정보 업뎃
                after_num.append(num_sum // len(temp))
                after_xy.append(temp)

    # print()
    # print('#####')
    # for line in check:
    #     print(line)


    ## 조건을 어떻게 표현할까 !
    ## => 각 연합에서 방문했던 위치들의 개수 -> 2개 이상인 연합그룹이 있다면 OK
    # result = list(len(case) for case in after_xy)
    # print('### 모든 연합 개수 :{0}'.format(result))
    # print(after_xy)



    #####if max(result) >= 2: # (주의) 생성된 연합이 있을 때 -> 인구이동이 일어남 O
    #####if max(result) >= 2 and result[0] != (n * n):
    if ok == True:
        # 인구이동 수행
        answer += 1  ## (비로소 인구이동이 수행된 것)

        for i in range(n):
            for j in range(n):
                group_idx = check[i][j]
                a[i][j] = after_num[group_idx]

        # print()
        # for line in a:
        #     print(line)

    else:
        break


print(answer)