BAEKJOON Online Judge(BOJ) 문제입니다.
문제
https://www.acmicpc.net/problem/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
- 강한 구현문제로 다른 코드를 참고하지 않음
기억해야할 것
'코딩테스트' 카테고리의 다른 글
[백준][브루트포스] 괄호 추가하기 (0) | 2022.05.02 |
---|---|
[백준][구현] 아기 상어 (0) | 2022.04.29 |
[백준][구현] 이차원 배열과 연산 (0) | 2022.04.29 |
[백준][구현] 연구소 3 (0) | 2022.04.29 |
[백준][구현] 게리멘더링 2 (0) | 2022.04.28 |