20057번 - 마법사 상어와 토네이도

문제

 

20057번: 마법사 상어와 토네이도 (acmicpc.net)

20057번: 마법사 상어와 토네이도

풀이 1

토네이도가 이동하며 흩뿌린 모래 중 격자 밖에 있는 모래양의 합을 출력해야 하므로, 보드 공간을 2만큼 양 옆 위 아래로 넓혀주면 편하다. 토네이도의 이동과 모래가 뿌려지는것을 구현하면 되고, 이는 마스킹과 같이 생각할 수 있다. 마스크 역할을 하는 토네이도는 반시계 방향으로 90도 돌릴필요가 있고, 두번 꺾을때 마다 이동거리가 1 씩 늘어난다. 종료조건에 따라 토네이도의 중심위치가 [0,0]에 다다르면 프로그램을 종료하되, 공간을 2만큼 넓혔으니 [2,2]를 그 조건으로 한다.

리뷰시 토네이도의 이동 및 마스킹을 중점적으로 보면 될것같다.

# 서,남,동,북
dRow = [0,1,0,-1]
dCol = [-1,0,1,0]

N = int(input())
board = [[0]*(N+4) for _ in range(2)]
for _ in range(N):
    board.append([0]*2 + list(map(int,input().split())) + [0]*2)
board.extend([[0]*(N+4) for _ in range(2)])

loc = [2+N//2,2+N//2]
# 속도,방향,cnt
state = [1,0,0]
tornado = [
    [0,0,0.02,0,0],
    [0,0.1,0.07,0.01,0],
    [0.05,0,0,0,0],
    [0,0.1,0.07,0.01,0],
    [0,0,0.02,0,0]
]


def set_tornado(row,col,dir):
    y = board[row][col]
    for r in range(5):
        for c in range(5):
            spr = int(y*tornado[r][c])
            board[row+r-2][col+c-2] += spr
            board[row][col] -= spr
    board[row + dRow[dir]][col + dCol[dir]] += board[row][col]
    board[row][col] = 0


def rotate_ccw_90(mat):
    new_mat = [[0]*5 for _ in range(5)]
    for row in range(5):
        for col in range(5):
            new_mat[row][col] = mat[col][5-row-1]
    return new_mat


def run_torado():
    global loc,tornado
    while True:
        # 토네이도 이동
        s,d,c = state
        for _ in range(s):
            loc = [loc[0]+dRow[d],loc[1]+dCol[d]]
            set_tornado(loc[0],loc[1],d)
            if loc == [2,2]:
                return
        # 토네이도 회전
        state[1] = (d+1)%4
        tornado = rotate_ccw_90(tornado)
        # 토네이도 속도 갱신
        state[2] += 1
        if state[2] == 2:
            state[2] = 0
            state[0] += 1


answer = 0
run_torado()
for row in range(N+4):
    for col in range(N+4):
        if not (2 <= row < N+2 and 2 <= col < N+2):
            answer += board[row][col]

print(answer)

풀이 2

단순히 중앙에서 출발해서 토네이도 이동 방향에 따라 마스킹을하는 문제이다. 딱히 주의할 점은 없으나, 시계 반대방향 회전은 코드와 같이 직접 구현해줘야한다. zip으로 할 수 있는것은 시계방향 회전 뿐이다.

#  동 남 서 북
dRow = [0,1,0,-1]
dCol = [1,0,-1,0]


N = int(input())
board = [[0]*(N+4) for _ in range(2)]
for _ in range(N):
    board.append([0,0] + list(map(int,input().split())) + [0,0])
for _ in range(2):
    board.append([0]*(N+4))

dirs = [-1] # (1,1) 은 도착지점으로 다음진행방향이 필요없음
visited = [[0]*N for _ in range(N)]
dir = 0
tr,tc,cr,cc = 0,0,N//2,N//2
while [tr,tc] != [cr,cc]:
    visited[tr][tc] = 1
    ntr,ntc = tr+dRow[dir],tc+dCol[dir]
    if not (0 <= ntr < N and 0 <= ntc < N and visited[ntr][ntc] == 0):
        dir = (dir+1)%4
        ntr,ntc = tr+dRow[dir],tc+dCol[dir]
    dirs.append((dir + 2) % 4) # 갱신된 방향의 반대 방향
    tr,tc = ntr,ntc
dirs.reverse()

# 곱해서 더해줄 비율
# 처음 방향은 서
tornado = [
    [0.0,0.0,0.02,0.0,0.0],
    [0.0,0.1,0.07,0.01,0.0],
    [0.05,0.0,0.0,0.0,0.0], # 중심점은 (2,2)
    [0.0,0.1,0.07,0.01,0.0],
    [0.0,0.0,0.02,0.0,0.0]
]

def rotate_ccw_90(mat):
    new_mat = [[0]*5 for _ in range(5)]
    for row in range(5):
        for col in range(5):
            new_mat[row][col] = mat[col][4-row]
    return new_mat


x,y = (N+4)//2,(N+4)//2

prev = dirs[0]
for dir in dirs:
    if dir == -1:
        break
    if dir != prev:
        tornado = rotate_ccw_90(tornado)
    nx,ny = x+dRow[dir],y+dCol[dir]
    ax,ay = nx+dRow[dir],ny+dCol[dir]
    sum_value = 0
    for i in range(-2,3,1):
        for j in range(-2,3,1):
            sand = int(board[nx][ny] * tornado[i+2][j+2])
            board[nx+i][ny+j] += sand
            sum_value += sand
    board[ax][ay] += board[nx][ny] - sum_value
    board[nx][ny] = 0
    prev = dir
    x,y = nx,ny

answer = 0
for row in range(N+4):
    for col in range(N+4):
        if not (2 <= row < N+2 and 2 <= col < N+2):
            answer += board[row][col]
print(answer)