20058. 마법사 상어와 파이어스톰 문제 바로가기
해결 방법
핵심 과정은 2가지 단계가 있다. (1. 회전하기 → 2. 얼음 녹이기)
회전하기 ★
위의 2가지 규칙을 이용하여 다음의 코드를 작성했다.
rotate_board[i + j2][j + 2 ** q - i2 - 1] = board[i + i2][j + j2]이때 규칙을 사용한 부분만 남겨두면 다음과 같다.
rotate_board[j2][2 ** q - i2 - 1] = board[i2][j2]즉, 기준이 되는 위치에 규칙을 적용시키면 원하는 동작을 할 수 있다.
얼음 녹이기
※ 주의 사항 : 회전한 보드 위에서 바로 녹이는 경우 안 녹는 얼음이 존재할 수 있기에 새로 0으로 초기화된 보드에 얼음 수를 저장해야 한다!
다음 Q만큼 반복한 뒤 최종적으로 남아있는 얼음 합과 가장 큰 덩어리를 차지하는 칸의 개수를 구하기 위해서 stack을 통해 DFS 로 찾았다.
구현한 코드
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
N, Q = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(2 ** N)]
Q_list = list(map(int, input().split()))
for q in Q_list:
# 1. 회전하기
rotate_board = [[0] * (2 ** N) for _ in range(2 ** N)]
for i in range(0, 2 ** N, 2 ** q):
for j in range(0, 2 ** N, 2 ** q):
# 회전 규칙 적용!
for i2 in range(2 ** q):
for j2 in range(2 ** q):
rotate_board[i + j2][j + 2 ** q - i2 - 1] = board[i + i2][j + j2]
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
# 2. 얼음 녹이기
board = [[0] * (2 ** N) for _ in range(2 ** N)]
for y in range(2 ** N):
for x in range(2 ** N):
cnt = 0
for d in range(4):
ny, nx = y + dirs[d][0], x + dirs[d][1]
if 0 <= ny < 2 ** N and 0 <= nx < 2 ** N and rotate_board[ny][nx] != 0:
cnt += 1
if rotate_board[y][x] > 0:
if cnt < 3:
board[y][x] = rotate_board[y][x] - 1
else:
board[y][x] = rotate_board[y][x]
# 3. 남아있는 얼음 합과 가장 큰 덩어리를 차지하는 칸의 개수 구하기
ice_sum = 0 # 남아있는 얼음 합에 대한 변수
ice_amount_list = [0] # 얼음 덩어리 개수를 저장할 리스트
visited = [[False] * (2 ** N) for _ in range(2 ** N)]
for y in range(2 ** N):
for x in range(2 ** N):
temp = []
if board[y][x] != 0 and visited[y][x] == False:
# stack 이용
temp.append([y, x])
visited[y][x] = True
ice_sum += board[y][x]
cnt = 1
while temp:
test = temp.pop()
ty, tx = test[0], test[1]
for d in range(4):
nty, ntx = ty + dirs[d][0], tx + dirs[d][1]
if 0 <= nty < 2 ** N and 0 <= ntx < 2 ** N and visited[nty][ntx] == False and board[nty][ntx] != 0:
temp.append([nty, ntx])
visited[nty][ntx] = True
ice_sum += board[nty][ntx]
cnt += 1
ice_amount_list.append(cnt)
print(ice_sum)
print(max(ice_amount_list))