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

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

23291번: 어항 정리

 

상당히 요구하는 것이 많은 문제입니다.

단계별로 하나씩 차근차근 밟으면 되는데

여기서 가장 난감한 부분으

'첫번째 어항 쌓기'입니다.

저는 이걸 어항을 말아올린다고 표현했는데요

처음 문제를 푸는 입장에서는

저게 무슨 소리인지하고 난감해합니다.

애당초, 어떻게 리스트를 말아서 올리냐고요...

한참을 고민하던 저는

우직하게

문제에서 요구하는데로

말아올리는 걸 택했습니다.

N*N행렬을 만들고

N-2열까지는 -1로 채워지고

N-1에 현재 물고기가 채워지는 걸로 초기화했습니다.

시작점인 start

말아올릴 기준이 되는 pivot

말아올릴 때 바닥길이인 turn_b

이 3가지를 구했습니다.

turn_b가 pivot이후의 길이(N-pivot)보다 길면

더이상 말지 못하게 했습니다.

이후, 나머지는 비교적

무난무난하게 풀었습니다.

다만, 저같은 경우에는

첫번째 이동

두번쨰 이동에서

분배와 어항배치 함수를

각각 다르게 구현했습니다.

첫번째는 -1이 많은 리스트고

두번째는 알맹이만 있는 리스트라

저같은 경우에는 2개를 따로 구현했습니다.

 

https://door-of-tabris.tistory.com/entry/%EB%B0%B1%EC%A4%80-20058%EB%B2%88-%EB%A7%88%EB%B2%95%EC%83%81%EC%96%B4%EC%99%80-%ED%8C%8C%EC%9D%B4%EC%96%B4%EC%8A%A4%ED%86%B0%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준 20058번] 마법상어와 파이어스톰(파이썬)

리스트를 분배하는 방법은

이 문제를 참고하시면 더 좋을 것 같습니다.

 

# 백준 23291 어항정리
from copy import deepcopy

N, K = map(int, input().split())

fish = list(map(int, input().split()))

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


def divide(fish):
    temp = deepcopy(fish)
    for x in range(N):
        for y in range(N):
            if fish[x][y] > 0:
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if nx < 0 or nx >= N or ny < 0 or ny >= N:
                        continue
                    if fish[nx][ny] > 0:
                        div = abs(fish[x][y] - fish[nx][ny]) // 5
                        if div > 0:
                            if fish[x][y] > fish[nx][ny]:
                                temp[x][y] -= div
                            else:
                                temp[x][y] += div

    return temp


def divide_2(fish):
    temp = deepcopy(fish)
    X = len(fish)
    Y = len(fish[0])
    for x in range(X):
        for y in range(Y):
            if fish[x][y] > 0:
                for d in range(4):
                    nx = x + dx[d]
                    ny = y + dy[d]
                    if nx < 0 or nx >= X or ny < 0 or ny >= Y:
                        continue
                    if fish[nx][ny] > 0:
                        div = abs(fish[x][y] - fish[nx][ny]) // 5
                        if div > 0:
                            if fish[x][y] > fish[nx][ny]:
                                temp[x][y] -= div
                            else:
                                temp[x][y] += div

    return temp


def re_po(fish):
    temp = []
    # 현재 공간의 시작점를 구한다
    start = 0
    for i in range(N):
        if fish[N - 1][i] != -1:
            break
        start += 1
    for y in range(start, N, 1):
        x = N - 1
        while fish[x][y] != -1:
            temp.append(fish[x][y])
            x -= 1

    return temp


def re_po_2(fish):
    temp = []
    X_len = len(fish)
    Y_len = len(fish[0])
    for y in range(Y_len):
        for x in range(X_len - 1, -1, -1):
            temp.append(fish[x][y])

    return temp


time = 0
while True:
    # 가장 적은 어항에 물고기 한마리를 넣는다.
    mi_fish = min(fish)
    for i in range(N):
        if fish[i] == mi_fish:
            fish[i] += 1

    # 어항 말아올림
    temp = []
    for i in range(N - 1):
        data = [-1] * N
        temp.append(data)
    temp.append(fish)
    while True:
        # 현재 공간의 시작점를 구한다
        start = 0
        for i in range(N):
            if temp[N - 1][i] != -1:
                break
            start += 1
        # print(start)
        # 말아올리는 기준점 찾기
        pivot = start + 1
        while temp[N - 2][pivot] != -1:
            pivot += 1
            if pivot == N:
                break
            # 혹시나 pivot이 칸을 넘기면 스탑.

        # 말아올릴 때 바닥
        x = N - 1
        turn_b = 1
        while temp[x][pivot - 1] != -1:
            x -= 1
            turn_b += 1
        # print(start)
        # print(pivot)
        # print(turn_b)
        # 말아올릴 바닥이  기준부터 나머지 까지의 바닥보다  크다면, break
        if turn_b - 1 > N - pivot:
            break

        # 그게 아니라면, 말이올린다.
        # 먼저, 어떤 걸 말아올릴지 list로 받아본다.
        turn = []
        for y in range(pivot - 1, -1, -1):
            for x in range(N - 1, N - turn_b - 1, -1):
                if temp[x][y] == -1:
                    continue
                turn.append(temp[x][y])
                temp[x][y] = -1

        # print(turn)
        for x in range(N - 2, N - 2 - (pivot - start), -1):
            for y in range(pivot, pivot + turn_b - 1):
                # print(x,y)
                temp[x][y] = turn.pop(0)

        # print(temp)
    # 어항 분배
    div = divide(temp)
    # print(div)
    # 어항 재배열
    re = re_po(div)
    # print(re)
    # 어항 공중부양
    sky = []
    # 첫칸 N//2까지 180도 턴해서 띄운다
    tmp = []
    for i in range(N // 2):
        tmp.append(re[i])
    tmp.reverse()
    sky.append(tmp)
    # 두번째 칸도 구한다
    tmp_2 = []
    for i in range(N // 2, N):
        tmp_2.append(re[i])
    sky.append(tmp_2)
    s_len = len(sky[0])
    mid = (s_len // 2) - 1
    sky_2 = []
    for x in range(len(sky) - 1, -1, -1):
        data = []
        for y in range(mid, -1, -1):
            data.append(sky[x][y])
        sky_2.append(data)

    # 두번째 칸도 구한다
    for x in range(len(sky) // 2 - 1, len(sky)):
        data = []
        for y in range(mid + 1, s_len):
            data.append(sky[x][y])
        sky_2.append(data)

    # print(sky_2)
    # 어항 분배
    div_2 = divide_2(sky_2)
    # print(div_2)
    # 어항 재배열
    re_2 = re_po_2(div_2)
    # print(re_2)
    fish = deepcopy(re_2)

    time += 1
    # print(fish)
    # 최대,최소가 K이하면 어항 그만 옮김
    min_fish = min(fish)
    max_fish = max(fish)
    if max_fish - min_fish <= K:
        break

print(time)

 

 

https://devlibrary00108.tistory.com/663

[백준][Python][2021 하반기 삼성 코딩테스트] 23291 어항정리

https://chldkato.tistory.com/199?category=876515 

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

https://velog.io/@heyksw/Python-%EB%B0%B1%EC%A4%80-platinum-23291-%EC%96%B4%ED%95%AD-%EC%A0%95%EB%A6%AC

[Python] 백준 / platinum / 23291 : 어항 정리

 

이 문제에 대한 다른 분들 풀이도 봤지만

'빡구현이 답이다'라는 결론이 나왔습니다.

여러 사람들 스타일도 봤지만

각자 스타일이 달라서 이해가 어려운 경우도 있었습니다.

그만큼 공부할 것이 많았던 문제였고

많은 걸 배워갔습니다.

 

 

++++

#백준 23291 어항정리
from copy import deepcopy

N,K=map(int,input().split())

fish=list(map(int,input().split()))

time=0

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

while True:
    #가장 적은 물고기칸에 1 추가
    min_fish=min(fish)
    for i in range(N):
        if fish[i]==min_fish:
            fish[i]+=1
    #말아올리기
    temp=[[-1]*N for _ in range(N-1)]
    temp.append(fish)
    start=1
    while True:
        tap=start-1
        height=0
        x=N-1
        while temp[x][tap]!=-1:
            height+=1
            x-=1
        #쌓아올린 게 더 크면 끝낸다
        if height>(N-start):
            break
        p=start-1
        turn=1
        while temp[N-1][p]!=-1 and p>=0:
            for y in range(height):
                temp[N-1-turn][start+y]=temp[N-1-y][p]
                temp[N-1-y][p]=-1
            p-=1
            turn+=1



        start+=height
    #인접한 어항으로 이동
    #인접한 어항에 대해 물고기 수 차이를 구하고
    #이 차이를 5로 나눈 몫을 d
    #d가 0보다 크면, 두 어항 중 물고기가 많은 곳의 d마리를 적은 곳으로 보낸다.
    temp2=deepcopy(temp)
    for x in range(N):
        for y in range(N):
            if temp[x][y]!=-1:

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

                    if nx<0 or nx>=N or ny<0 or ny>=N:
                        continue
                    if temp[nx][ny]==-1:
                        continue

                    move=abs(temp[x][y]-temp[nx][ny])
                    move//=5

                    if move>0:
                        if temp[nx][ny]>temp[x][y]:
                            temp2[nx][ny]-=move
                        else:
                            temp2[nx][ny]+=move
    #어항다시 일자로
    fish=[]
    start=0
    while temp2[N-1][start]==-1:
        start+=1

    for y in range(start,N):
        x=N-1
        while temp2[x][y]!=-1:
            fish.append(temp2[x][y])
            x-=1

    #다른 공중부양
    temp3=[]
    data=[]
    for y in range(N//2-1,-1,-1):
        data.append(fish[y])
    temp3.append(data)
    data=[]
    for y in range(N//2,N):
        data.append(fish[y])
    temp3.append(data)


    temp4=[]
    for x in range(1,-1,-1):
        data=[]
        for y in range(N//4-1,-1,-1):
            data.append(temp3[x][y])
        temp4.append(data)
    for x in range(2):
        data=[]
        for y in range(N//4,N//2):
            data.append(temp3[x][y])
        temp4.append(data)
    temp5=deepcopy(temp4)
    #분배해주기
    x_len=len(temp4)
    y_len=len(temp4[0])
    for x in range(x_len):
        for y in range(y_len):
            for d in range(4):
                nx=x+dx[d]
                ny=y+dy[d]
                if nx<0 or nx>=x_len or ny<0 or ny>=y_len:
                    continue

                move=abs(temp4[nx][ny]-temp4[x][y])
                move//=5

                if move>0:
                    if temp4[nx][ny]>temp4[x][y]:
                        temp5[nx][ny]-=move
                    else:
                        temp5[nx][ny]+=move

    #일자로 피기
    fish=[]
    for y in range(y_len):
        for x in range(x_len-1,-1,-1):
            fish.append(temp5[x][y])
    time+=1

    #조건
    if max(fish)-min(fish)<=K:
        break

print("{}".format(time))

다시 풀었던 코드입니다.

저는 이번에 풀 때에는

하나 하나 구현할 때마다

print를 해준 후 맞게 되었는지 확인했습니다.

이 문제가 체감난이도 대비

정답률이 높은 걸 생각해보면

'그대로 구현하면 맞는다'는 유형이기 때문입니다.

물론 모든 구현/시뮬레이션이

문제에서 요구하는 데로 똑같이 구현하면 풀리지만

유독 이 문제의 경우에는

반례가 없었던 케이스입니다.

그래서 연습을 하는 입장에서는

시간만 주어진다면

그래도 그럭저럭 풀 수 있습니다.

다만, 이런 문제를 시험장에서 만났을 때에는

시간적 압박때문에 쉽게 풀기는 힘든 문제라고 느껴지네요.