마법사 상어와 토네이도
- 난이도 : 골드 3
- 소요시간 : 약 50분
이런 가운데서 회오리 모양으로 나가는 좌표 문제는 블리자드였나? 거기서 푼 적이 있어서 당황 스럽지는 않았다.
모래가 흩날리는 것을 회전해서 해도 되겠다고 생각은 됐는데, 그냥 4방향 밖에 없어서 수작업으로 하는게 낫겠다 싶었다.
그래서 그냥 수작업으로 구현해주니까 맞았다. 어렵지는 않았는데 저렇게 나선형으로 나가는 좌표를 처리 할 줄 모르면 상당히 까다로웠을 것 같다.
코드는 엄청긴데, 사실 한 방향만 해놓으면 나머지 방향은 그냥 거저먹기라..
정답 코드
N = int(input())
graph = []
for _ in range(N):
graph.append(list(map(int,input().split())))
# y행, x열
# alpha : 45%
def check(xx,yy):
if 0<=xx<N and 0<=yy<N:
return True
return False
def left(cx,cy):
global graph
alpha = [0,-1]
queue = [[-1,-1,0.1],[-1,0,0.07], [-2,0,0.02],[-1,1,0.01],[1,1,0.01],[1,0,0.07],[2,0,0.02],[1,-1,0.1],[0,-2,0.05]]
current_dust = graph[cy][cx]
total_dust = current_dust
graph[cy][cx] = 0
out_dust = 0
for q in queue:
ny, nx, p = cy + q[0], cx + q[1], q[2]
value = int(current_dust * p)
total_dust -= value
#밖으로 나가면
if check(nx,ny):
graph[ny][nx] += value
else:
#아니면
out_dust += value
ny = cy + alpha[0]
nx = cx + alpha[1]
if check(nx,ny):
graph[ny][nx] += total_dust
else:
out_dust += total_dust
return out_dust
def right(cx,cy):
alpha = [0,1]
queue = [[1,1,0.1],[-1, 0, 0.07], [-2, 0, 0.02], [1, -1, 0.01], [-1, -1, 0.01], [1, 0, 0.07], [2, 0, 0.02], [-1, 1, 0.1], [0, 2, 0.05]]
current_dust = graph[cy][cx]
total_dust = current_dust
graph[cy][cx] = 0
out_dust = 0
for q in queue:
ny, nx, p = cy + q[0], cx + q[1], q[2]
value = int(current_dust * p)
total_dust -= value
# 밖으로 나가면
if check(nx, ny):
graph[ny][nx] += value
else:
# 아니면
out_dust += value
ny = cy + alpha[0]
nx = cx + alpha[1]
if check(nx, ny):
graph[ny][nx] += total_dust
else:
out_dust += total_dust
return out_dust
def down(cx,cy):
alpha = [1, 0]
queue = [[0,-1,0.07],[0,-2,0.02],[-1,-1,0.01],[-1,1,0.01],[0,1,0.07],[0,2,0.02],[1,1,0.1],[2,0,0.05],[1,-1,0.1]]
current_dust = graph[cy][cx]
total_dust = current_dust
graph[cy][cx] = 0
out_dust = 0
for q in queue:
ny, nx, p = cy + q[0], cx + q[1], q[2]
value = int(current_dust * p)
total_dust -= value
# 밖으로 나가면
if check(nx, ny):
graph[ny][nx] += value
else:
# 아니면
out_dust += value
ny = cy + alpha[0]
nx = cx + alpha[1]
if check(nx, ny):
graph[ny][nx] += total_dust
else:
out_dust += total_dust
if cy == 3 and cx == 2:
print(total_dust)
print(out_dust)
print(current_dust)
return out_dust
def up(cx,cy):
alpha = [-1,0]
queue = [[0,-1,0.07],[0,-2,0.02],[1,1,0.01],[1,-1,0.01],[0,1,0.07],[0,2,0.02],[-1,1,0.1],[-2,0,0.05],[-1,-1,0.1]]
current_dust = graph[cy][cx]
total_dust = current_dust
graph[cy][cx] = 0
out_dust = 0
for q in queue:
ny, nx, p = cy + q[0], cx + q[1], q[2]
value = int(current_dust * p)
total_dust -= value
# 밖으로 나가면
if check(nx, ny):
graph[ny][nx] += value
else:
# 아니면
out_dust += value
ny = cy + alpha[0]
nx = cx + alpha[1]
if check(nx, ny):
graph[ny][nx] += total_dust
else:
out_dust += total_dust
return out_dust
# 1, 2, 3, 4: 왼 아 오 위
def init_tor():
arr = []
init_y = (N-1)//2
init_x = (N-1)//2
cur_y = init_y
cur_x = init_x
for n in range(3,N+1):
if n % 2 == 0:
continue
cur_x -= 1
arr.append([cur_y,cur_x,1])
for _ in range(n-2):
cur_y += 1
arr.append([cur_y,cur_x,2])
for _ in range(n-1):
cur_x += 1
arr.append([cur_y,cur_x,3])
for _ in range(n-1):
cur_y -= 1
arr.append([cur_y,cur_x,4])
for _ in range(n-1):
cur_x -= 1
arr.append([cur_y,cur_x,1])
return arr
tor = init_tor() # 토네이도의 이동 방향, 좌표가 담겨있는 함수
answer = 0
for y,x,d in tor:
if d == 1:
answer += left(x,y)
elif d == 2:
answer += down(x,y)
elif d == 3:
answer += right(x,y)
elif d == 4:
answer += up(x,y)
print(answer)마법사 상어와 파이어스톰
- 난이도 : 골드 4
아마 가장 까다로웠던 건 격자를 나누는 방식이랑, 나눈 격자를 돌리는 것, 이렇게 두가지였다.
만약에 시험장에서 이러한 부분을 만난다면, 종이에 차근차근 볼펜으로 계산해보면 잘 나올 것 같다.
이 두가지 처리만 잘한다면 나머지는 무난하다. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수는 BFS로 구하면 된다.
from collections import deque
N, Q = map(int,input().split())
n = pow(2,N) # 2^N
ices = []
for _ in range(n):
inp = list(map(int,input().split()))
ices.append(inp)
level = list(map(int,input().split()))
# ---- 입력 끝 ----
graph = ices
temp = [[0] * n for _ in range(n)]
# temp[x][(길이 - 1) - y]
# 90 도 회전
def rotate(start_x,start_y,d):
global temp
global graph
for cy in range(d):
for cx in range(d):
temp[start_y + cx][start_x + (d-1) - cy] = graph[start_y + cy][start_x+cx]
for cy in range(d):
for cx in range(d):
graph[start_y + cx][start_x + (d-1)-cy] = temp[start_y + cx][start_x + (d-1)-cy]
def check(kx,ky):
if 0<=kx<n and 0<=ky<n:
return True
return False
delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
q = Q
while q > 0:
l = level[Q-q]
q -= 1
expl = pow(2,l) # 격자 한 변의 길이
max_y = n // expl # 격자가 한 변에 차는 갯수
init_y = 0
# 격자로 나눠서 돌리기
if l != 0:
for yy in range(max_y):
# init_y, init_x : 격자 별 시작 좌표(왼쪽 위)
init_x = 0
while init_x < n:
rotate(init_x, init_y, expl)
init_x += expl
init_y += expl
delta = [[0,1],[0,-1],[1,0],[-1,0]]
will_destroy = []
for y in range(n):
for x in range(n):
ice_count = 0
for d in delta:
ny = y + d[0]
nx = x + d[1]
if not check(nx,ny):
continue
if graph[ny][nx] != 0:
ice_count += 1
if ice_count < 3:
will_destroy.append([y,x])
# 얼음 양 줄어든다.
while will_destroy:
wy, wx = will_destroy.pop()
if graph[wy][wx] > 0:
graph[wy][wx] -= 1
isvisited = [[False] * n for _ in range(n)]
answer = 0
# 남아있는 얼음의 합
for y in range(n):
for x in range(n):
answer += graph[y][x]
max_block = 0
for y in range(n):
for x in range(n):
if isvisited[y][x]:
continue
if graph[y][x] == 0:
continue
queue = deque([])
queue.append([y,x])
block = 1
while queue:
cy, cx = queue.popleft()
isvisited[cy][cx] = True
for d in delta:
ny = cy + d[0]
nx = cx + d[1]
if not check(nx,ny):
continue
if not isvisited[ny][nx] and graph[ny][nx] != 0:
block += 1
isvisited[ny][nx] = True
queue.append([ny,nx])
max_block = max(max_block,block)
print(answer)
print(max_block)
Hongik CE