149. [삼성기출45]Python 백준 23291 어항 정리
안녕하세요 코딩하는 덕구입니다.
파이썬 백준 23291 어항 정리 입니다.
https://www.acmicpc.net/problem/23291
23291번: 어항 정리
마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바
www.acmicpc.net
문제 접근
구현문제다. 구현 중 가장 까다로운 것은 행렬의 회전이었다.
90도 회전과 180도 회전을 구현해야 된다.
1. 180도 회전은 1차원 리스트에서만 적용하므로, 리스트를 거꾸로 접근하면 180도 회전과 같다.
2. 90도 우회전은 직접 구현했다.
N*M리스트를 우회전 시키려면 회전전의 성분이 회전후에 어디로 가는지 살펴보면 된다.
회전전의 가장 아래의 행부터 위의 순서대로, 첫번째 열의 성분이
회전후의 첫번째 행이 된다.
이해하기 어렵다면 square에 아무 행렬이나 넣고 직접 이 코드를 돌려보는 것을 추천한다.
new = [[x[i] for x in reversed(square)] for i in range(len(square[0]))]
문제는 이렇게 해결했다.
def solve():
cnt = 1
global square
while True:
add_fishes()
stack()
turn_right()
mk_board()
adjust()
flatten()
turn_right2()
adjust()
flatten()
if max(fish_bowls) - min(fish_bowls) <= K:
return cnt
square = []
cnt += 1
print(solve())어항 리스트에 한번만 접근하고 싶어서 아래와 같이 코드를 작성했다.
1. 최솟값과 같다면 후보 리스트에 index를 추가한다.
2. 지금까지의 최솟값보다 작다면 리스트를 초기화한다.
3. 최솟값보다 크다면 무시한다.
만들어진 리스트의 index에 접근해 물고기 수를 늘린다.
def add_fishes():
min_index = []
minimum = 1e9
for i, fishes in enumerate(fish_bowls):
if fishes < minimum:
min_index = [i]
minimum = fishes
elif fishes == minimum:
min_index.append(i)
for i in min_index:
fish_bowls[i] += 1
square는 회전시킬 행렬이다.
def stack():
global square
square.append([fish_bowls.popleft()])
본격적으로 회전을 시킨다. 여기서는 회전시킨 행렬과 어항을 분리된 상태에서 진행한다. 어항과 행렬은 다음 함수에서 합친다.
회전후의 밑변이 어항의 길이보다 작으면 행렬을 회전시킨다.
1. 쌓여있는 길이만큼 어항을 잘라서 square의 밑변에 붙인다.
2. 우회전 시킨다.
def turn_right():
global square
height = len(square) + 1
while height <= len(fish_bowls) - len(square[0]):
#1. 밑변 잘라서 합치기
tmp = []
for _ in range(len(square[0])):
tmp.append(fish_bowls.popleft())
square.append(tmp)
#2. 우회전
new = [[x[i] for x in reversed(square)] for i in range(len(square[0]))]
square = new
height = len(square) + 1
회전이 끝난 행렬과 어항을 합치는 함수다. 합쳐야 상하좌우 살피면서 물고기의 마리수를 업데이트하기 좋다.
빈칸은 0을 넣어서 깔끔한 직사각형으로 만들었다.
def mk_board():
global board
board = [[0 for _ in range(len(fish_bowls))] for _ in range(len(square) + 1)]
for i in range(len(square)):
for j in range(len(square[0])):
board[i][j] = square[i][j]
board[-1] = fish_bowls
물고기 마리수를 업데이트 하는 함수다. 한번에 업데이트 해야되므로 deepcopy해줬다.
상하좌우 살피면서 좌표가 범위 내에 있고, 물고기가 존재하면 문제에서 말하는 d, 코드에서는 k를 구했다.
5로 나눈 몫을 구해 0 보다 크면 k마리만큼 이동시켰다.
def adjust():
global board
tmp = deepcopy(board)
for x in range(len(board)):
for y in range(len(board[0])):
if board[x][y] == 0:
continue
for d in range(4):
nx, ny = dx[d] + x, dy[d] + y
if 0 <= nx < len(board) and 0 <= ny < len(board[0]):
if board[nx][ny] != 0:
k = (board[x][y] - board[nx][ny]) // 5
if k > 0:
tmp[x][y] -= k
tmp[nx][ny] += k
board = tmp
2차원 리스트를 1차원으로 만드는 함수다.
맨 밑에서부터 0이 나올 때 까지 좌표를 올려가며 새로운 리스트에 삽입해줬다.
def flatten():
global fish_bowls
tmp = deque()
for j in range(len(board[0])):
for i in range(len(board)-1, -1, -1):
if board[i][j] == 0:
break
tmp.append(board[i][j])
fish_bowls = tmp
2번째 회전이다.
1차원 리스트의 180도 회전은 행렬을 그냥 거꾸로 접근하면 된다.
90도 회전은 처음과 같이 1차원 행렬을 밑에다 더해 2차원 행렬로 만들고, 회전시켰다.
def turn_right2():
global board
square = deque()
for _ in range(N//2):
square.append(fish_bowls.popleft())
square.reverse()
tmp1 = []
tmp2 = []
for _ in range(N//4):
tmp1.append(square.popleft())
tmp2.append(fish_bowls.popleft())
new = [tmp1, tmp2]
for _ in range(2):
new = [[x[i] for x in reversed(new)] for i in range(len(new[0]))]
new.append(list(square))
new.append(list(fish_bowls))
board = new
Python 정답 코드
백준 23291 파이썬 코드입니다.
from collections import deque
from copy import deepcopy
N, K = map(int, input().split())
fish_bowls = deque(map(int, input().split()))
square = []
board = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def add_fishes():
min_index = []
minimum = 1e9
for i, fishes in enumerate(fish_bowls):
if fishes < minimum:
min_index = [i]
minimum = fishes
elif fishes == minimum:
min_index.append(i)
for i in min_index:
fish_bowls[i] += 1
def stack():
global square
square.append([fish_bowls.popleft()])
def turn_right():
global square
height = len(square) + 1
while height <= len(fish_bowls) - len(square[0]):
#1. 밑변 잘라서 합치기
tmp = []
for _ in range(len(square[0])):
tmp.append(fish_bowls.popleft())
square.append(tmp)
#2. 우회전
new = [[x[i] for x in reversed(square)] for i in range(len(square[0]))]
square = new
height = len(square) + 1
def mk_board():
global board
board = [[0 for _ in range(len(fish_bowls))] for _ in range(len(square) + 1)]
for i in range(len(square)):
for j in range(len(square[0])):
board[i][j] = square[i][j]
board[-1] = fish_bowls
def adjust():
global board
tmp = deepcopy(board)
for x in range(len(board)):
for y in range(len(board[0])):
if board[x][y] == 0:
continue
for d in range(4):
nx, ny = dx[d] + x, dy[d] + y
if 0 <= nx < len(board) and 0 <= ny < len(board[0]):
if board[nx][ny] != 0:
k = (board[x][y] - board[nx][ny]) // 5
if k > 0:
tmp[x][y] -= k
tmp[nx][ny] += k
board = tmp
def flatten():
global fish_bowls
tmp = deque()
for j in range(len(board[0])):
for i in range(len(board)-1, -1, -1):
if board[i][j] == 0:
break
tmp.append(board[i][j])
fish_bowls = tmp
def turn_right2():
global board
square = deque()
for _ in range(N//2):
square.append(fish_bowls.popleft())
square.reverse()
tmp1 = []
tmp2 = []
for _ in range(N//4):
tmp1.append(square.popleft())
tmp2.append(fish_bowls.popleft())
new = [tmp1, tmp2]
for _ in range(2):
new = [[x[i] for x in reversed(new)] for i in range(len(new[0]))]
new.append(list(square))
new.append(list(fish_bowls))
board = new
def debug():
for i in range(len(board)):
for j in range(len(board[0])):
print(board[i][j], end=" ")
print()
print()
def solve():
cnt = 1
global square
while True:
add_fishes()
stack()
turn_right()
mk_board()
adjust()
flatten()
turn_right2()
adjust()
flatten()
if max(fish_bowls) - min(fish_bowls) <= K:
return cnt
square = []
cnt += 1
print(solve())
백준 23291 Python 코드였습니다.
감사합니다.