알고리즘/백준
[백준] 17144번: 미세먼지 안녕!
Ynghan
2024. 1. 15. 22:36
문제 이해
R(행) × C(열)을 입력으로 받고, T(초)를 입력받는다.
R × C 크기 만큼의 숫자를 입력 받는다.
이때, 1번 째 열에 공기청정기가 설치되고 -1로 나타낸다.
확산
순환
문제 풀기
from sys import stdin
from typing import List
ccw = globals()
def rotate(A: List[List[int]]) -> List[List[int]]:
for i in range(ccw-2, -1, -1):
A[i+1][0] = A[i][0]
for i in range(0,C,1):
A[0][i] = A[0][i+1]
for i in range(0,ccw):
A[i][-1] = A[i+1][-1]
for i in range(C,1,-1):
A[ccw][i] = A[ccw][i-1]
A[ccw][0] = -1
A[cw][0] = -1
return A
def spread(A: List[List[int]]) -> List[List[int]]:
# 상 하 좌 우
x = [0, 0, -1, 1]
y = [1, -1, 0, 0]
new_A = List[List[int]]
for i in range(R):
for j in range(C):
if A[i][j] == 0:
continue
for k in range(4):
if R > i + x[k] >= 0 and j + y[k] <= C and i + x[k] != ccw and j + y[k] != 0:
new_A[i + x[k]][j + y[k]] = A[i][j] // 5
A[i][j] -= new_A[i + x[k]][j + y[k]] // 5
A += new_A
return A
input = stdin.readline
R, C, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(R)]
ccw = 0
for i in range(R):
if A[i][0] == -1:
ccw = i
break
cw = ccw - 1
for _ in range(T):
spread(A)
rotate(A)
total = sum(A)
print(total)- 순환을 위한 rotate 메소드
- 확산을 위한 spread 메소드
코드 수정
전체 구조 코드
수정 전
R, C, T = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(R)]
ccw = 0
for i in range(R):
if A[i][0] == -1:
ccw = i
break
cw = ccw - 1
for _ in range(T):
spread(A)
rotate(A)
total = sum(A)
print(total)수정 후
r, c, t = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(r)]
for i in range(r):
if board[i][0] == -1:
ccw, cw = i, i + 1
break
for _ in range(t):
board = spread()
rotate()
print(sum([sum(line) for line in board]) + 2) # 공기청정기 -1 * 2 고려- 변수명 변경 : A → board
- ccw, cw 대입 방식 변경
- spread() 함수는 board를 따로 생성하지 않고 반환하기 때문에 board에 직접 대입
- 2차원 배열 매개변수로 사용 → 매개 변수 없이 메소드 호출
- 잘못된 집계 함수 방식 수정
spread(확산) 메소드
수정 전
def spread(A: List[List[int]]) -> List[List[int]]:
# 상 하 좌 우
x = [0, 0, -1, 1]
y = [1, -1, 0, 0]
new_A = List[List[int]]
for i in range(R):
for j in range(C):
if A[i][j] == 0:
continue
for k in range(4):
if R > i + x[k] >= 0 and j + y[k] <= C and i + x[k] != ccw and j + y[k] != 0:
new_A[i + x[k]][j + y[k]] = A[i][j] // 5
A[i][j] -= new_A[i + x[k]][j + y[k]] // 5
A += new_A
return A수정 후
def spread():
"""
미세 먼지 확산 결과 반환 함수
"""
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
new_board = [[0] * c for _ in range(r)]
new_board[ccw][0] = -1
new_board[cw][0] = -1
for x in range(r):
for y in range(c):
if board[x][y] > 0:
new_board[x][y] += board[x][y]
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < r and 0 <= ny < c and board[nx][ny] != -1:
new_board[nx][ny] += board[x][y] // 5
new_board[x][y] -= board[x][y] // 5
return new_board- 변수명 : new_A → new_board
- 공기 청정기 위치 설정 : new_board[ccw][0] = -1 ....
- new_board에 확산된 값만 넣도록 했음 → new_board에 기존 값을 더한 이후 확산 값을 계산하도록 했음
- 반복문 변수를 x와 y로 사용함 → 가독성
- 기존 코드는 0 이외의 값을 필터링하지 못하여 공기 청정기를 필터링 하지 못하였다. 수정된 코드는 0 초과의 값만 필터링하여 공기 청정기를 필터링할 수 있게 하였다.
rotate() 메소드
수정 전
def rotate(A: List[List[int]]) -> List[List[int]]:
for i in range(ccw-2, -1, -1):
A[i+1][0] = A[i][0]
for i in range(0,C,1):
A[0][i] = A[0][i+1]
for i in range(0,ccw):
A[i][-1] = A[i+1][-1]
for i in range(C,1,-1):
A[ccw][i] = A[ccw][i-1]
A[ccw][0] = -1
A[cw][0] = -1
return A수정 후
def rotate():
"""
미세 먼지 순환 함수
"""
# 위쪽 순환: 반시계 방향
for x in range(ccw - 1, 0, -1):
board[x][0] = board[x - 1][0]
for y in range(c - 1):
board[0][y] = board[0][y + 1]
for x in range(ccw):
board[x][-1] = board[x + 1][-1]
for y in range(c - 1, 0, -1):
board[ccw][y] = board[ccw][y - 1]
# 아래쪽 순환: 시계 방향
for x in range(cw + 1, r - 1):
board[x][0] = board[x + 1][0]
for y in range(c - 1):
board[-1][y] = board[-1][y + 1]
for x in range(r - 1, cw, -1):
board[x][-1] = board[x - 1][-1]
for y in range(c - 1, 0, -1):
board[cw][y] = board[cw][y - 1]
# 공기청정기에서 나온 바람은 미세 먼지가 없는 바람이므로 0으로 초기화
board[ccw][1] = 0
board[cw][1] = 0위쪽 순환만 코드 작성했었음.
공기청정기에서 나오는 바람을 생각하지 못하였음.
매우 틀린 부분이 많았다.