[BOJ] 23291. 어항 정리 (💎, 구현/시뮬레이션)

🔗

풀이

1차원 배열이 2차원이 됐다가 다시 1차원이 되는 과정을 반복하며 배열을 돌리는 시뮬레이션 문제. 정답률이 높은 걸 보면 문제만 잘 읽으면 틀릴 일 없을 거 같았다.

1. 물고기 수가 가장 적은 칸들에 1씩 추가한다
2. 불가능할 때까지 어항을 쌓는다
3. 물고기의 수를 조절한다
4. 한 줄로 만든다
5. 반으로 자라서 180도 회전한다. 두 번 반복한다.
6. 물고기 수를 조절한다.
7. 다시 한 줄로 만든다

어항 쌓기

가장 왼쪽의 한 칸을 시작으로 어항을 쌓아서 올리는 과정을 반복한다.

어항이 쌓여있는 부분들만 모아서 90도를 회전한다. 그림에서는 위로 쌓이는 걸로 표현되지만 코드 상에서는 좀 더 편하게 구현할 수 있도록 아래로 쌓았다.

[
	[9, 3, 11, 8]
	[14, 5]
	[3, 3]
]

기본적으로 쌓인 어항은 2차원 배열로 나타난다. [[9, 3], [14, 5], [3, 3]] 의 3행 2열 배열만 떼어내서 90도 회전시켜야 한다. 규칙을 생각해보면 가장 마지막 행의 열 길이만큼만 모든 행에 대해서 떼어내면 된다는 걸 알 수 있다. 그렇게 만들어진 2차원 배열은 90도 회전하여 다시 남은 배열의 아래에 추가한다.

# 배열 떼어내기
def detach(arr, r, k):
    tmp = []
    for i in range(r-1):
        tmp.append(arr.pop())
    tmp.append(arr[0][:k])
    arr[0] = arr[0][k:]
    return tmp, arr
    
# 첫 번째 어항 쌓기(90도 회전)
def stack(arr):
    arr.append([arr[0].pop(0)])
    
    while True:
        r, c, k = len(arr), len(arr[0]), len(arr[-1])
        if c-k<r:
            break
        tmp, arr = detach(arr, r, k)
        arr.extend(rotate(tmp))
    return arr

물고기 수 조절

모든 칸에 대해서 상하좌우를 다 비교해야 한다. 하지만 이렇게 비교하다보면 겹치는 칸에 대해서 예외처리를 해야 하므로, 쉽게 비교하기 위해서 모든 칸에 대해서 오른쪽과 아래쪽에 대해서만 비교를 수행한다. 어차피 둘 중 2개의 칸에 대해서 모두 비교할 필요 없이 둘 중 하나의 칸에 대해서만 비교하면 되기 때문. 비교를 하는 도중에 숫자가 변경되면 안 되기 때문에 증가하거나 감소하는 값들에 대해서는 임시 배열에 저장해야 한다.

def fish_control(arr):
    n = len(arr)
    tmp = [[0]*len(arr[i]) for i in range(n)]

    for i in range(n):
        m = len(arr[i])
        for j in range(m):
            for ni, nj in (i-1, j), (i, j+1):
                if not(-1<ni<n and -1<nj<m):
                    continue
                
                mod = abs(arr[i][j] - arr[ni][nj])//5
                if mod < 0:
                    continue
                if arr[i][j] > arr[ni][nj]:
                    tmp[ni][nj] += mod
                    tmp[i][j] -= mod
                else:
                    tmp[i][j] += mod
                    tmp[ni][nj] -= mod
    
    for i in range(n):
        for j in range(len(arr[i])):
            arr[i][j] += tmp[i][j]
    return arr

공중부양

절반만큼 잘라서 180도 위로 쌓는 작업을 2번만 반복하면 된다.

def levitation(arr):
    for i in range(2):
        tmp = []
        k = len(arr[0])//2
        for j in range(len(arr)-1, -1, -1):
            tmp.append(arr[j][:k][::-1])
            arr[j] = arr[j][k:]
        arr.extend(tmp)
    return arr

일렬로 만들기

배열을 떼어내서 다시 일렬로 만든다.

def make_row(arr):
    tmp, lst = detach(arr, len(arr), len(arr[-1]))
    arr = []
    for row in rotate(tmp)[::-1]:
        arr.extend(row)
    arr.extend(*lst)
    return [arr]

최종 코드

# 어항 정리 : 44ms (Python3)

# 회전
def rotate(arr):
    return list(map(list, zip(*arr[::-1])))[::-1]

# 가장 작은 물고기의 어항에 1추가
def minimum_fish(arr):
    min_v = min(arr[0])
    for i in range(len(arr[0])):
        if arr[0][i] == min_v:
            arr[0][i] += 1
    return arr

# 어항 떼어내서 돌리기 
def detach(arr, r, k):
    tmp = []
    for i in range(r-1):
        tmp.append(arr.pop())
    tmp.append(arr[0][:k])
    arr[0] = arr[0][k:]
    return tmp, arr

# 첫 번째 어항 쌓기
def stack(arr):
    arr.append([arr[0].pop(0)])
    
    while True:
        r, c, k = len(arr), len(arr[0]), len(arr[-1])
        if c-k<r:
            break
        tmp, arr = detach(arr, r, k)
        arr.extend(rotate(tmp))
    return arr

# 물고기 수 조절
def fish_control(arr):
    n = len(arr)
    tmp = [[0]*len(arr[i]) for i in range(n)]

    for i in range(n):
        m = len(arr[i])
        for j in range(m):
            for ni, nj in (i-1, j), (i, j+1):
                if not(-1<ni<n and -1<nj<m):
                    continue
                
                mod = abs(arr[i][j] - arr[ni][nj])//5
                if mod < 0:
                    continue
                if arr[i][j] > arr[ni][nj]:
                    tmp[ni][nj] += mod
                    tmp[i][j] -= mod
                else:
                    tmp[i][j] += mod
                    tmp[ni][nj] -= mod
    
    for i in range(n):
        for j in range(len(arr[i])):
            arr[i][j] += tmp[i][j]
    return arr

# 일렬로 만들기
def make_row(arr):
    tmp, lst = detach(arr, len(arr), len(arr[-1]))
    arr = []
    for row in rotate(tmp)[::-1]:
        arr.extend(row)
    arr.extend(*lst)
    return [arr]

# 공중 부양 
def levitation(arr):
    for i in range(2):
        tmp = []
        k = len(arr[0])//2
        for j in range(len(arr)-1, -1, -1):
            tmp.append(arr[j][:k][::-1])
            arr[j] = arr[j][k:]
        arr.extend(tmp)
    return arr

n, k = map(int, input().split())
arr = [list(map(int, input().split()))]
count = 0

while True:
    if max(arr[0]) - min(arr[0]) <= k:
        print(count)
        break
    
    arr = make_row(fish_control(levitation(make_row(fish_control(stack(minimum_fish(arr)))))))
    count += 1