Python/구현 BOJ-23291 어항정리

Posted on | In

[Python/구현] BOJ-23291 어항정리

📌문제링크 풀이참고

*풀이참고 링크 들어가셔서 보시면 됩니다.

물고기가 가장 많이 들어있는 어항과 가장 적게 들어있는 어항의 물고기 수 차이가 K 이하가 되려면 어항을 몇 번 정리해야하는지 출력하면 된다. 어렵다 어려워,,,,,여태껏 푼 문제중에 제일 어렵다. 시험장에서 만났다면 정말 뇌절 각이다. 지금 만난걸 다행이라 생각하자 ^_^!

아래 접근 순서대로 차분히 짜보자.

[접근]

  1. 최소값에 1 더하기
  2. 일렬로 정렬된 어항을 굴려서 쌓기 - roll_1
  3. 인접된 어항에 대해 물고기수 차이를 5로 나눈 몫 d를 구함 - fish_arrange
  4. 몫이 0보다 크면 두 어항중 물고기 수가 많은 곳에 있는 물고기 d 마리를 적은곳에 있는 곳으로 보냄 - fish_arrange
  5. 일렬로 어항을 푼다. - unflod
  6. 다시 쌓는 작업 진행 후 물고기 재정렬 - roll_2
  7. 몫이 0보다 크면 두 어항중 물고기 수가 많은 곳에 있는 물고기 d 마리를 적은곳에 있는 곳으로 보냄 - fish_arrange
  8. 일렬로 어항을 푼다. - unflod

​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import sys
from collections import deque
from typing import Match 

input = sys.stdin.readline
N,K =map(int,input().split())
arr = list(map(int,input().split()))
delta = ((0, -1), (-1, 0), (0, 1), (1, 0))

pivot = N//4
for i in range(2,11):
    if i**2 >=N:
        n=i
        break


def add_minimum(arr):
    min_val = min(arr)
    for i in range(N) :
        if arr[i] == min_val :
            arr[i] +=1


def roll_1():
    row,col = n,n
    if n**2 - N >=n :
        col -=1
    matrix =[[0]*col for _ in range(row)]
    q = deque()
    q.append((row-1,col-1,0))
    blank_cnt = row*col -N
    start = N-1
    while q :
        x, y, d = q.popleft()
        matrix[x][y] = arr[start]
        if blank_cnt:
            matrix[x][y] = -1
        for i in range(d,d+4) :
            i %= 4
            nx,ny = x+delta[i][0], y +delta[i][1]
            if 0 <= nx < row and 0 <= ny < col and not matrix[nx][ny] :
                q.append((nx,ny,i))
                if blank_cnt:
                    blank_cnt-=1
                else:
                    start -=1
                break
    return matrix

def fish_arrange(matrix):
    row = len(matrix)
    col = len(matrix[0])
    new_matrix = [[0] * col for _ in range(row)]
    if matrix[-1][-1] == -1:
        row -= 1
        a, b = row - 1, row
        if matrix[a][0] != -1 and matrix[b][0] != -1:
            if matrix[a][0] < matrix[b][0]:
                a, b = b, a
            move = (matrix[a][0] - matrix[b][0]) // 5
            new_matrix[a][0] -= move
            new_matrix[b][0] += move
        for y in range(col):
            if matrix[row][y] == -1:
                break
            for dy in (1, -1):
                ny = y + dy
                if 0 <= ny < col and matrix[row][ny] != -1:
                    if matrix[row][y] - matrix[row][ny] < 5:
                        continue
                    move = (matrix[row][y] - matrix[row][ny]) // 5
                    new_matrix[row][ny] += move
                    new_matrix[row][y] -= move 
    for x in range(row):
        for y in range(col):
            for dx, dy in delta:
                nx, ny = x + dx, y + dy
                if 0 <= nx < row and 0 <= ny < col:
                    if matrix[x][y] - matrix[nx][ny] < 5:
                        continue
                    move = (matrix[x][y] - matrix[nx][ny]) // 5
                    new_matrix[nx][ny] += move
                    new_matrix[x][y] -= move
    if matrix[-1][-1] == -1:
        row += 1
    for i in range(row):
        for j in range(col):
            matrix[i][j] += new_matrix[i][j]
    return matrix

def make_arr(matrix):
    row = len(matrix)
    col = len(matrix[0])
    ret = []
    if matrix[-1][-1] == -1:
        for i in range(row):
            for j in range(col):
                if matrix[i][j] == -1:
                    continue
                ret.append(matrix[i][j])
    else:
        for i in range(col):
            for j in range(row - 1, -1, -1):
                ret.append(matrix[j][i])
    return ret


def make_four_row(arr):
    new_matrix = []
    new_matrix.append(arr[pivot * 2:pivot * 3][::-1])
    new_matrix.append(arr[pivot:pivot * 2])
    new_matrix.append(arr[:pivot][::-1])
    new_matrix.append(arr[pivot * 3:])
    return new_matrix


ans =0
while max(arr)-min(arr) > K :
    add_minimum(arr)
    matrix = roll_1()
    matrix = fish_arrange(matrix)
    arr = make_arr(matrix)
    matrix = make_four_row(arr)
    matrix = fish_arrange(matrix)
    arr = make_arr(matrix)
    ans += 1

print(ans)

회고

굴리는 로직이 전혀 머리속에 떠오르지 않아서 애먹었다.
답을 보지 않고서는 풀지 못하는 수준이였다.