반응형
https://www.acmicpc.net/problem/20058
20058번: 마법사 상어와 파이어스톰
마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c
www.acmicpc.net
<문제 풀이>
- 남아있는 얼음의 합, 가장 큰 덩어리가 차지하는 칸의 수를 구하는 구현문제였다.
- 조건에 따라 차례대로 구현을 진행했다.
- 회전하는 부분이 헷갈렸다. for문 말고 딱히 어떻게 표현해야 할지 몰라서...
- 그 이외에는 특별한게 없었고 얼음 덩어리 찾는 곳에서는 BFS를 사용하여 덩어리를 찾았고 max로 갱신하면서 진행했다.
<Code>
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
length = 2**N
ice = [list(map(int, input().split())) for _ in range(2**N)]
L_list = list(map(int, input().split()))
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
for L in L_list:
# 회전하기
t = 2**L
for i in range(0, length, t):
for j in range(0, length, t):
temp = [ice[_][j:j+t] for _ in range(i, i+t)]
for n in range(t):
for m in range(t):
ice[i+m][j+t-1-n] = temp[n][m]
# temp에 인접한 얼음 갯수 표기
temp = [[0]*length for _ in range(length)]
for i in range(length):
for j in range(length):
for k in range(4):
y = i + dy[k]
x = j + dx[k]
if 0 <= y < length and 0 <= x < length and ice[y][x]:
temp[i][j] += 1
# 인접한 얼음 개수가 3개 미만 이면 얼음 녹이기
for i in range(length):
for j in range(length):
if ice[i][j] > 0 and temp[i][j] < 3:
ice[i][j] -= 1
print(sum(sum(i) for i in ice)) # 남은 얼음의 합
# 얼음 덩어리 찾기
ice_cube = 0
for i in range(length):
for j in range(length):
if ice[i][j]:
q = [[i, j]]
ice[i][j] = 0
cnt = 1
while q:
a, b = q.pop()
for k in range(4):
y = a + dy[k]
x = b + dx[k]
if 0 <= y < length and 0 <= x < length and ice[y][x]:
q.append([y, x])
ice[y][x] = 0
cnt += 1
ice_cube = max(ice_cube, cnt)
print(ice_cube)
※ 잘못된 점, 개선점 등이 있다면 언제든 댓글로 알려주시면 감사하겠습니다.
![](https://t1.daumcdn.net/keditor/emoticon/niniz/large/010.gif)
반응형
'Alogorithm > BAEKJOON' 카테고리의 다른 글
[BAEKJOON] 2293 동전 1 - Python (0) | 2023.05.09 |
---|---|
[BAEKJOON] 20057 마법사 상어와 토네이도 - Python (0) | 2023.04.08 |
[BAEKJOON] 23290 마법사 상어와 복제 - Python (0) | 2023.03.30 |
[BAEJOON] 21611 마법사 상어와 블리자드 - Python (0) | 2023.03.29 |
[BAEKJOON] 21610 마법사 상어와 비바라기 - Python (0) | 2023.03.28 |