[백준][구현] 미세먼지 안녕!

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

https://www.acmicpc.net/problem/17144

17144번: 미세먼지 안녕!

 

내가 작성한 코드

from collections import defaultdict, deque

dir = [(0, 1), (0, -1), (-1, 0), (1, 0)]

def in_range(r, c, R, C):
    return 0 <= r < R and 0 <= c < C

def read_data():
    R, C, T = map(int, input().rstrip().split())
    board = []
    cleaner = None
    for r in range(R):
        board.append(list(map(int, input().rstrip().split())))
        for c in range(C):
            if cleaner is None and board[r][c] == -1:
                cleaner = (r, c)

    return R, C, T, board, cleaner

def get_route(cleaner, R, C):
    def make_q(r, c, ds, q):
        nw_r, nw_c = r, c
        for d in ds:
            nw_r, nw_c = nw_r + dir[d][0], nw_c + dir[d][1]
            while in_range(nw_r, nw_c, R, C) and not (nw_r == r and nw_c == c):
                q.append((nw_r, nw_c))
                nw_r, nw_c = nw_r + dir[d][0], nw_c + dir[d][1]
            nw_r, nw_c = nw_r - dir[d][0], nw_c - dir[d][1]

    r, c = cleaner

    upper = []
    lower = []

    # upper
    ds = [0, 2, 1, 3]
    make_q(r, c, ds, upper)

    # lower
    ds = [0, 3, 1, 2]
    make_q(r+1, c, ds, lower)

    return upper, lower

def expand(board, R, C):
    q = defaultdict(int)
    for r in range(R):
        for c in range(C):
            if board[r][c] >= 5:
                total = 0

                for d_r, d_c in dir:
                    nw_r, nw_c = r+d_r, c+d_c
                    if in_range(nw_r, nw_c, R, C) and board[nw_r][nw_c] != -1:
                        v = board[r][c] // 5
                        total += v
                        q[(nw_r, nw_c)] += v

                board[r][c] -= total

    for k, v in q.items():
        r, c = k
        board[r][c] += v

def operate(board, upper, lower):
    v = 0
    for r, c in upper:
        board[r][c], v = v, board[r][c]

    v = 0
    for r, c in lower:
        board[r][c], v = v, board[r][c]


def get_sum(board, R, C):
    total = 2
    for r in range(R):
        for c in range(C):
            total += board[r][c]
    return total

def get_answer(R, C, T, board, cleaner):
    upper, lower = get_route(cleaner, R, C)

    for _ in range(T):
        expand(board, R, C)
        operate(board, upper, lower)

    return get_sum(board, R, C)

def test():
    R, C, T = 50, 50, 1000
    board = [[0 for _ in range(C)] for _ in range(R)]
    board[30][0] = -1
    board[31][0] = -1
    for i in range(50):
        board[i][i] = 1000
    cleaner = None
    for r in range(R):
        for c in range(C):
            if cleaner is None and board[r][c] == -1:
                cleaner = (r, c)

    return R, C, T, board, cleaner


R, C, T, board, cleaner = read_data()
# R, C, T, board, cleaner = test()
print(get_answer(R, C, T, board, cleaner))

• Pypy로 제출해야 통과

 

다른 사람이 작성한 코드

None

• 강한 구현문제로 다른 코드를 참고하지 않음

 

기억해야할 것