17144번 - 미세먼지 안녕!

문제

 

17144번: 미세먼지 안녕! (acmicpc.net)

17144번: 미세먼지 안녕!

풀이 1

유형이 구현 그 자체인 문제이다. 핵심은 올바르게 지시사항을 구현하는것이다...! 코드가 길어지며 잘못 인덱싱하는 부분은 없는지 신경쓰며 코드를 작성하면 쉽게 해결 가능한 문제이다.

from collections import deque

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

R,C,T = map(int,input().split())
purifier = []
board = []
for row in range(R):
    li = list(map(int, input().split()))
    if li[0] == -1:
        purifier.append(row)
    board.append(li)
a1,a2 = deque(maxlen=2*(C+(purifier[0]-1))-1),deque(maxlen=2*(C+(R-purifier[1]-2))-1)

for _ in range(T):
    # 확산
    new_board = [[*elem] for elem in board]
    for row in range(R):
        for col in range(C):
            if board[row][col] > 0:
                cnt = 0
                for i in range(4):
                    nRow,nCol = row+dRow[i],col+dCol[i]
                    if 0 <= nRow < R and 0 <= nCol < C and not (nRow in purifier and nCol == 0):
                        new_board[nRow][nCol] += board[row][col] // 5
                        cnt += 1
                new_board[row][col] -= (board[row][col] // 5) * cnt
    board = [[*elem] for elem in new_board]
    # 공기청정기
    a1 += board[purifier[0]][1:C-1] + [board[i][C-1] for i in range(purifier[0],0,-1)] + board[0][C-1:0:-1] + [board[i][0] for i in range(purifier[0])]
    a2 += board[purifier[1]][1:C-1] + [board[i][C-1] for i in range(purifier[1],R-1)] + board[-1][C-1:0:-1] + [board[i][0] for i in range(R-1,purifier[1],-1)]
    a1.appendleft(0)
    a2.appendleft(0)
    # 윗 부분 반시계 회전
    for col in range(1,C-1):
        board[purifier[0]][col] = a1.popleft()
    for row in range(purifier[0],0,-1):
        board[row][C-1] = a1.popleft()
    for col in range(C-1,0,-1):
        board[0][col] = a1.popleft()
    for row in range(0,purifier[0]):
        board[row][0] = a1.popleft()
    # 아랫 부분 시계 회전
    for col in range(1,C-1):
        board[purifier[1]][col] = a2.popleft()
    for row in range(purifier[1],R-1):
        board[row][C-1] = a2.popleft()
    for col in range(C-1,0,-1):
        board[R-1][col] = a2.popleft()
    for row in range(R-1,purifier[1],-1):
        board[row][0] = a2.popleft()

print(sum(map(sum,board))+2)

풀이 2

공기청정기 바람의 진행경로를 슬라이싱 대신 직접 경로를 구현하는 방식으로 풀이했다.

from collections import deque

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

R,C,T = map(int,input().split())
A = [[0] * (C + 1) for _ in range(R + 1)]
cr = []
cc = []
for i in range(R):
    for j,v in enumerate(map(int,input().split())):
        A[i + 1][j + 1] = v
        if v == -1:
            cr.append(i+1)
            cc.append(j+1)


def get_conv(conv,part):
    dir = 0
    i,j = [0,1] if part == 1 else [1,3]
    r,c = cr[i],cc[i]
    while True:
        nr,nc = r+dRow[dir],c+dCol[dir]
        if [nr,nc] == [cr[i],cc[i]]:
            break
        if not (1 <= nr <= R and 1 <= nc <= C):
            dir = (dir+j)%4
            nr,nc = r+dRow[dir],c+dCol[dir]
        conv.append(A[nr][nc])
        r,c = nr,nc
    return conv


def update_board(conv,part):
    dir = 0
    i,j = [0,1] if part == 1 else [1,3]
    r,c = cr[i],cc[i]
    for e in conv:
        nr, nc = r + dRow[dir], c + dCol[dir]
        if not (1 <= nr <= R and 1 <= nc <= C):
            dir = (dir + j) % 4
            nr, nc = r + dRow[dir], c + dCol[dir]
        A[nr][nc] = e
        r, c = nr, nc


for _ in range(T):
    # 미세먼지 확산
    new_A = [[*elem] for elem in A]
    for row in range(1,R+1):
        for col in range(1,C+1):
            if A[row][col] >= 5:
                diff = A[row][col] // 5
                cnt = 0
                for i in range(4):
                    nRow,nCol = row+dRow[i],col+dCol[i]
                    if 1 <= nRow <= R and 1 <= nCol <= C and A[nRow][nCol] != -1:
                        new_A[nRow][nCol] += diff
                        new_A[row][col] -= diff
    A = [[*elem] for elem in new_A]
    # 공기청정기 작동
    # 위
    conv_1 = deque(maxlen = cr[0]*C - (cr[0]-2)*(C-2) - 1)
    conv_1 = get_conv(conv_1, 1)
    conv_1.appendleft(0)
    update_board(conv_1,1)
    # 아래
    conv_2 = deque(maxlen = (R-cr[0])*C - (R-cr[0]-2)*(C-2) - 1)
    conv_2 = get_conv(conv_2, 2)
    conv_2.appendleft(0)
    update_board(conv_2,2)

answer = sum(map(sum,A)) + 2
print(answer)