[Python] 백준 23291 어항 정리

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

# 23291 어항 정리

# 상 하 좌 우
dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

def rotate(x, y):
    temp_grounds = [[0] * x for _ in range(y)]

    for r in range(x):
        for c in range(y):
            temp_grounds[c][x - r - 1] = cur_grounds[r][c]
    return temp_grounds


def make_one():
    global grounds
    temp_grounds = list()
    for r in range(len(grounds)):
        for c in range(len(grounds[0])):
            if grounds[r][c] != -1:
                temp_grounds.append(grounds[r][c])

    grounds = temp_grounds
    return

def cal_fish():
    global grounds
    temp_grounds = [[0] * len(grounds[0]) for _ in range(len(grounds))]
    for r in range(len(grounds)):
        for c in range(len(grounds[0])):
            if grounds[r][c] == -1:
                continue
            for i in range(4):
                cr = r + dr[i]
                cc = c + dc[i]
                # 범위 내에 있다면
                if 0 <= cr < len(grounds) and 0 <= cc < len(grounds[0]):
                    if grounds[cr][cc] == -1:
                        continue
                    cur_num = grounds[r][c] - grounds[cr][cc]
                    cur_num //= 5
                    if cur_num <= 0:
                        continue
                    temp_grounds[cr][cc] += cur_num
                    temp_grounds[r][c] -= cur_num

    for r in range(len(grounds)):
        for c in range(len(grounds[0])):
            grounds[r][c] += temp_grounds[r][c]
    return


N, K = map(int, input().split())
fishes = list(map(int, input().split()))
grounds = [[fish] for fish in fishes]
result = 0

while True:
    # 물고기 수 최소, 최대 어항 구하기
    minimum = 10001
    maximum = 0
    for ground in grounds:
        minimum = min(ground[0], minimum)
        maximum = max(ground[0], maximum)
    if maximum - minimum <= K:
        break
    result += 1

    # 최소인 어항 += 1
    for i in range(len(grounds)):
        if grounds[i][0] == minimum:
            grounds[i][0] += 1

    # 가장 왼쪽에 있는 어항을 오른쪽 위에 올리기
    up_ground = grounds.pop(0)
    grounds[0].extend(up_ground)

    # 2개 이상 쌓여있는 어항을 모두 공중부양, 시계 방향으로 90도 회전
    while True:
        idx = 0
        while len(grounds[idx]) >= 2:
            idx += 1
            if len(grounds) - idx < len(grounds[0]):
                break

        # 높이가 남은 어항 길이보다 크면 계속 진행
        if len(grounds) - idx < len(grounds[0]):
            break

        cur_grounds = list()
        for _ in range(idx):
            cur_grounds.append(grounds.pop(0))

        ready_grounds = rotate(idx, len(cur_grounds[0]))
        for i in range(len(ready_grounds)):
            grounds[i].extend(ready_grounds[i])

    # 높이 맞추기 위해서 0 padding 추가
    height = len(grounds[0])
    for i in range(len(grounds)):
        while len(grounds[i]) < height:
            grounds[i].append(-1)

    # 모든 인접한 두 어항에 대해서 물고기 수의 차이를 구한다.
    cal_fish()

    # 일렬로 펴기
    make_one()

    # 가운데 중심으로 N/2개 공중부양시켜 180도 회전, 오른쪽 N/2개 위에 놓아야 한다.
    for _ in range(2):
        idx = len(grounds) // 2
        temp_grounds = list()
        # 숫자 세기
        while idx:
            temp_grounds.append(grounds.pop(0))
            idx -= 1

        # 두 번째 진입은 list로 함 - 돌려서 넣어주기
        if type(temp_grounds[0]) == list:
            rever_temp = [[0] * len(temp_grounds[0]) for _ in range(len(temp_grounds))]
            for i in range(len(temp_grounds)):
                for j in range(len(temp_grounds[0])):
                    rever_temp[i][j] = temp_grounds[i][len(temp_grounds[0]) - j - 1]

            # 180도 돌려서 넣기
            for i in range(len(grounds)):
                grounds[i].extend(rever_temp.pop())
        # 첫 번째 진입이라면
        else:
            # 남은 그라운드 임의로 list로 만들어주기.
            grounds = [[ground] for ground in grounds]
            # 180도 돌려서 넣기
            for i in range(len(grounds)):
                grounds[i].append(temp_grounds.pop())

    # 물고기 조절 작업하기
    cal_fish()

    # 일렬로 펴기
    make_one()

    grounds = [[ground] for ground in grounds]


print(result)

자세한 리뷰는 나중에 마음이 내킬 때 하겠다.

첫 플레티넘 풀이에 성공하였다. 만세!

헤맨 부분

90도 회전시킬 때, 맨 위, 왼쪽이 (0, 0), 맨 위, 오른쪽이(0, c - 1), 맨 아래, 오른쪽이(r - 1, c - 1)이어야 한다는 편견에 사로잡혔다.

처음 문제풀이를 시도했을 때는, 이 때문에 잘 풀지 못했다.

두 번째 문제를 풀기 전과 푸는 과정에서 이 문제를 인지하고, 문제 조건에 맞게 맨 아래 왼쪽이 (0, 0), 맨 위 왼쪽이 (0, c - 1), 맨 위 오른쪽이(r - 1, c - 1) 처럼 되는 것을 인지한 후에 풀었다.

pycharm에서 돌려보던 중, 에러가 있는 부분을 발견했다.

while len(grounds[idx]) >= 2:
    idx += 1

while 부분에서 에러가 났다. print를 찍어본 뒤, grounds의 index가 초과될 수 있음을 인지하고 다음과 같이 수정하였다.

while len(grounds[idx]) >= 2:
    idx += 1
    if len(grounds) - idx < len(grounds[0]):
        break

플레티넘 명성에 맞게 엄청 어렵지는 않았다. (사실 이제 한 문제 푼 사람이 난이도를 매기는 것도 웃기다.) 하지만, 낯선 환경인 실전에서 1시간 30분 내에 이 문제를 풀기는 정말 쉽지 않을 것 같다.

처음 문제를 풀 때 1시간 30분 가량을 소모한 뒤 결국 회전에서 막혔고,
두 번째 시도에서 대략 1시간 10~20분만에 푼 것 같다.

더 정확하고 빠르게 풀 수 있도록, 반복숙달해야겠다.