[python] BOJ 백준 23291: 어항정리

1. 문제  

마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바닥 위에 놓여져 있다. 어항에는 물고기가 한 마리 이상 들어있다. <그림 1>은 어항 8개가 바닥 위에 놓여있는 상태이며, 칸에 적힌 값은 그 어항에 들어있는 물고기의 수이다. 편의상 어항은 정사각형으로 표현했다.

어항을 한 번 정리하는 과정은 다음과 같이 이루어져 있다.

먼저, 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 만약, 그러한 어항이 여러개라면 물고기의 수가 최소인 어항 모두에 한 마리씩 넣는다. 위의 예시의 경우 물고기의 수가 가장 적은 어항에는 물고기가 2마리 있고, 그러한 어항은 2개가 있다. 따라서, 2개의 어항에 물고기를 한 마리씩 넣어 <그림 2>와 같아진다.

이제 어항을 쌓는다. 먼저, 가장 왼쪽에 있는 어항을 그 어항의 오른쪽에 있는 어항의 위에 올려 놓아 <그림 3>이 된다.

이제, 2개 이상 쌓여있는 어항을 모두 공중 부양시킨 다음, 전체를 시계방향으로 90도 회전시킨다. 이후 공중 부양시킨 어항을 바닥에 있는 어항의 위에 올려놓는다. 바닥의 가장 왼쪽에 있는 어항 위에 공중 부양시킨 어항 중 가장 왼쪽에 있는 어항이 있어야 한다. 이 작업은 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 있을때까지 반복한다.

먼저, <그림 4>와 같이 어항이 놓인 상태가 변하고, 한 번 더 변해서 <그림 5>가 된다.

<그림 5>에서 한 번 더 어항을 공중 부양시키는 것은 불가능하다. 그 이유는 <그림 6>과 같이 공중 부양시킨 어항 중 가장 오른쪽에 있는 어항의 아래에 바닥에 있는 어항이 없기 때문이다. 공중 부양 작업이 모두 끝나면, 어항에 있는 물고기의 수를 조절한다.

모든 인접한 두 어항에 대해서, 물고기 수의 차이를 구한다. 이 차이를 5로 나눈 몫을 d라고 하자. d가 0보다 크면, 두 어항 중 물고기의 수가 많은 곳에 있는 물고기 d 마리를 적은 곳에 있는 곳으로 보낸다. 이 과정은 모든 인접한 칸에 대해서 동시에 발생한다. 이 과정이 완료되면 <그림 7>이 된다.

이제 다시 어항을 바닥에 일렬로 놓아야 한다. 가장 왼쪽에 있는 어항부터, 그리고 아래에 있는 어항부터 가장 위에 있는 어항까지 순서대로 바닥에 놓아야 한다. <그림 8>이 바닥에 다시 일렬로 놓은 상태이다.

여기서 다시 위에서 한 물고기 조절 작업을 수행하고, 바닥에 일렬로 놓는 작업을 수행한다. <그림 10>에서 조절 작업을 마친 결과는 <그림 11>이 되고, 여기서 다시 바닥에 일렬로 놓는 작업을 수행하면 <그림 12>가 된다.

어항의 수 N, 각 어항에 들어있는 물고기의 수가 주어진다. 물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 구해보자.

2. 입력   

첫째 줄에 N, K가 주어진다. 둘째에는 어항에 들어있는 물고기의 수가 가장 왼쪽에 있는 어항부터 순서대로 주어진다.

3. 출력   

물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 출력한다.

 

4. 해결방법   

삼성에서 자주 출제되는 시뮬레이션 문제이다. 문제에서 제시된 순서에 맞게 코드를 짜면되고, 별다른 로직이나 자료구조를 사용할 필요는 없다. 다만, 배열을 회전하는 과정에서 약간 까다로울수 있는 문제이다. 

1) spread 함수: 인접한 어항끼리의 차이를 계산하고, 전파된 배열을 반환하는 함수이다. 모든 전파는 동시다발적으로 일어나므로, copy라이브러리를 사용한 깊은 복사가 필수이다. 주의해야할 점은, 배열이 정직한 직사각형이 아닐수 있다는 점이다. 맨밑 행의 배열의 길이가 더 클 수 있기 때문에 조건문을 이용하여 인덱스 오류가 나지않게 설정해야한다. 또한, 가로와 세로 모두 전파가 일어나므로 두가지의 경우 각각에 대해서 계산을 해주어야한다. 

2) make_line 함수: 쌓인 어항을 다시 한줄로 세울때 사용하는 함수이다. 길이가 2 이상인 배열들에 대해서 1인 배열로 쪼개준다. 

3) 메인함수에서는 회전과 공중부양에 대한 코드를 작성하였다. 첫번째 단계에 해당하는 90도 회전인 경우에는 index 기준을 통해 어디까지 쌓고 멈출지를 결정해주어야한다. (그림 6 참고) 두번째 단계에 해당하는 18-도 회전인 경우에는 따로 설정해줄 필요는 없다. N이 4의배수인 경우만 입력으로 주어지기 때문이다. 이 전체과정을 무한루프 돌리면서, 배열의 최대값 최소값 차이가 k보다 적으면 무한루프를 멈추고 고 카운트 수를 반환해주면 된다. 

 

5) 구현코드       

import sys
from copy import deepcopy

n, k = map(int, input().split())
a = list(map(int, input().split()))
fish = [[] for _ in range(n)]
for i in range(n):
    fish[i].append(a[i])


#인접한 어항 계산 
def spread(n, fish): 
    fish_temp = deepcopy(fish)
    for i in range(n):
        if fish[i]:
            for j in range(len(fish[i])):
                #세로 전파
                if i + 1 < len(fish):
                    if j < len(fish[i + 1]):
                        if fish[i + 1][j]:
                            d = abs(fish[i][j] - fish[i + 1][j]) // 5
                            if fish[i][j] > fish[i + 1][j]:
                                fish_temp[i][j] -= d
                                fish_temp[i + 1][j] += d
                            elif fish[i][j] < fish[i + 1][j]:
                                fish_temp[i][j] += d
                                fish_temp[i + 1][j] -= d
                #가로 전파 
                if j + 1 < len(fish[i]):
                    d = abs(fish[i][j] - fish[i][j + 1]) // 5
                    if fish[i][j] > fish[i][j + 1]:
                        fish_temp[i][j] -= d
                        fish_temp[i][j + 1] += d
                    elif fish[i][j] < fish[i][j + 1]:
                        fish_temp[i][j] += d
                        fish_temp[i][j + 1] -= d
    return fish_temp


#한줄로 만들기
def make_line():
    blank_idx = 0
    for i in range(n):
        if len(fish[i]) > 1:
            temp = fish[i]
            fish[i] = []
            for k in temp:
                fish[blank_idx].append(k)
                blank_idx += 1


cnt = 1
while True:
    #가장 작은 어항 +1 
    min_value = 10000
    for i in range(len(fish)):
        min_value = min(fish[i][0], min_value)
    for i in range(len(fish)):
        if fish[i][0] == min_value:
            fish[i][0] += 1
 

    fish[1].append(fish[0][0])
    fish[0] = []
 

    flag = 0 
    while True:
        for i in range(len(fish)-1, 0, -1):
            if len(fish[i]) > 1:
                #더이상 쌓을수 없는 경우에는 Stop
                if len(fish[i]) > len(fish) - i - 1:
                    flag = 1
                    break
                for j in range(i + 1, n):
                    if fish[j]:
                      #90도회전
                        for v, idx in zip(fish[i], range(j, j + len(fish[i]) + 1)):
                            fish[idx].append(v)
                        break
                fish[i] = []
        if flag == 1:
            break

    fish = spread(n, fish) #전파
    make_line() #한줄로만들기

    #N/2개를 공중 부양
    left, right = fish[:n//2], fish[n//2:]
    n_left = left[-1::-1]
    for l, r in zip(n_left, right): #180도회전
        r.append(l[0])

    #N/4개를 공중 부양
    left, right = right[:n//4], right[n//4:]
    for _ in range(2): #180도회전 
        left = list(zip(*left[::-1]))
    for l, r in zip(left, right):
        for ll in l:
            r.append(ll)

    right = spread(n//4, right) #전파 

    fish = [[] for _ in range(n)]
    for i in range(len(right)):
        fish[-i-1] = right[len(right) - i -1]
    make_line()

    max_n, min_n = 0, 10000
    for f in fish:
        max_n = max(f[0], max_n)
        min_n = min(f[0], min_n)

    if max_n - min_n <= k:
        print(cnt)
        break

    cnt += 1

 

⭐️난이도:  플레티넘5⭐️ 

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

23291번: 어항 정리

참고한 블로그: https://chldkato.tistory.com/199?category=876515 

백준 23291 어항 정리 (파이썬)