Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- ODEs
- 공수
- 삼성SW역량테스트
- 공수 문제풀이
- vocabulary
- Problem Set 1.4
- English
- Homogeneous ODEs
- SW역량테스트
- 코딩테스트
- homogeneous
- 대학
- 문제풀이
- kreyszig
- 공수1
- Python
- 맛집
- 비제차 상미분 방정식
- Nonhomogeneous ODEs
- Ode
- 미방
- 영어회화
- Problem set 2.7
- Problem set 1.5
- Advanced Engineering Mathematics
- 공업수학
- 미분방정식
- 공학수학
- Conversation
- 백준
Archives
- Today
- Total
한걸음
[220925] 백준 20058 : 마법사 상어와 파이어스톰 본문
반응형
https://www.acmicpc.net/problem/20058
1. 보드판 일부 떼어내서 회전시키기
다음과 같은 3 x 3 형태의 배열을 생각해보자
시계 방향으로 90도 회전할 경우 1행의 정보는 3열로 이동할 것이고, 3행의 정보는 1열로 이동할 것이다. 따라서, 배열의 마지막 행부터 불러와서 temp 배열에 append 해주면 90도 시계방향으로 회전한 것과 같은 효과를 볼 수 있다.
def rotate(arr):
temp = [[] for _ in range(len(arr))]
for row in range(len(arr)-1, -1, -1): # 한 행을 불러와서
for col in range(len(arr[row])-1, -1, -1) :
# 아래서 부터 채운다. 위에서 부터 채워도 상관없다.
temp[col].append(arr[row][col])
return temp
매번 배열을 불러올 때, 시작점과 끝점들을 기록해두었다가 회전한 이후에 다시 보드판에 업데이트하면 된다.
rot_arr = []
for i in range(0, 2**N, 2**L):
temp_arr = board[i : i + 2**L]
for j in range(0, 2**N, 2**L) :
for k in temp_arr :
rot_arr.append(k[j : j + 2**L])
x0, x1, y0, y1 = int(i), int(i + 2**L), int(j), int(j + 2**L)
rot_arr = rotate(rot_arr)
ix, iy = 0, 0
for xxx in range(x0, x1):
iy = 0
for yyy in range(y0, y1):
board[xxx][yyy] = rot_arr[ix][iy]
iy += 1
ix += 1
if ix >= abs(x1 - x0) : ix = 0
rot_arr = []
2. 얼음 줄이기
"이후 얼음이 있는 칸 3개 또는 그 이상과 인접해있지 않은 칸은 얼음의 양이 1 줄어든다."
말을 참 어렵게 해 놨다. 이해하기 쉽게 표현하면,
"자기 위치에서 상하좌우 인접한 칸에 얼음이 2개 이하일 경우에 얼음이 감소한다."
정도로 해석이 가능할 것 같다. (한편으로는 보드판 경계 밖을 고려해서 이렇게 말한 것 같기도 하다.)
※ 주의! ※
여기서 이미 얼음 다 녹아서 없어졌는데, 무작정 -1 하는 일은 없도록 하자
3. 전체 코드
메모리 : 123796 KB, 시간 : 1016ms, 풀이 시간 : 102분
N, Q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(2**N)]
L_info = list(map(int, input().split()))
# 북, 동, 남, 서
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def rotate(arr):
temp = [[] for _ in range(len(arr))]
for row in range(len(arr)-1, -1, -1): # 한 행을 불러와서
for col in range(len(arr[row])-1, -1, -1) :
# 아래서 부터 채운다. 위에서 부터 채워도 상관없다.
temp[col].append(arr[row][col])
return temp
def diminish():
temp = []
for i in range(2**N):
for j in range(2**N):
x, y = i, j
cnt = 0
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < 2**N and 0 <= ny < 2**N and board[nx][ny] > 0 :
cnt += 1
if cnt < 3 :
temp.append([x, y])
while temp :
x, y = temp[0]
del temp[0]
if board[x][y] > 0 :
board[x][y] -= 1
def bfs():
# 가장 큰 덩어리 찾기
visited = [[False for _ in range(2**N)] for _ in range(2**N)]
maxValue = 0
for i in range(2**N):
for j in range(2**N):
if board[i][j] > 0 and not visited[i][j] :
q = [[i, j]]
visited[i][j] = True
cnt = 1
while q :
x, y = q[0]
del q[0]
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < 2 ** N and 0 <= ny < 2 ** N and not visited[nx][ny] :
if board[nx][ny] > 0 :
cnt += 1
visited[nx][ny] = True
q.append([nx, ny])
maxValue = max(maxValue, cnt)
return maxValue
def solve():
it = 0
while it < Q :
L = L_info[it]
rot_arr = []
for i in range(0, 2**N, 2**L):
temp_arr = board[i : i + 2**L]
for j in range(0, 2**N, 2**L) :
for k in temp_arr :
rot_arr.append(k[j : j + 2**L])
x0, x1, y0, y1 = int(i), int(i + 2**L), int(j), int(j + 2**L)
rot_arr = rotate(rot_arr)
ix, iy = 0, 0
for xxx in range(x0, x1):
iy = 0
for yyy in range(y0, y1):
board[xxx][yyy] = rot_arr[ix][iy]
iy += 1
ix += 1
if ix >= abs(x1 - x0) : ix = 0
rot_arr = []
diminish()
it += 1
total = 0
for i in range(2**N):
total += sum(board[i])
result = bfs()
print(total)
print(result)
solve()
반응형
'Coding Test' 카테고리의 다른 글
[221001] 백준 21608 : 상어 초등학교 (0) | 2022.10.01 |
---|---|
[221001] 백준 20061 : 모노미노도미노 2 (0) | 2022.10.01 |
[220926] 백준 21610 : 마법사 상어와 비바라기 (1) | 2022.09.26 |
[220925] 백준 4179 : 불! (0) | 2022.09.25 |
[220925] 백준 3055 : 탈출 (1) | 2022.09.25 |