Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- 투포인터 알고리즘
- 1753 파이썬
- 1644 파이썬
- 백준 10819
- 백준 5582
- 안드로이드 hilt
- 백준 1644
- 1003 파이썬
- Jetpack Room
- 5582 DP
- 이진 탐색
- 1806 백준
- Android Room
- 2096 파이썬
- 5582 파이썬
- Android mvp
- flow buffering
- 1806 파이썬
- 자바
- Coroutine Flow
- java
- 1753 다익스트라
- android hilt
- 백준 2096
- 10819 파이썬
- 1806 투포인터
- 6588 파이썬
- 자료구조
- 코루틴 플로우
- git local remote
Archives
- Today
- Total
Gemstone's Devlog
[백준] 17144번: 미세먼지 안녕! (구현, 시뮬레이션) 본문
https://www.acmicpc.net/problem/17144
17144번: 미세먼지 안녕!
미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사
www.acmicpc.net




교양시간에 수업은 안듣고 solved.ac Class4 문제들을 뒤적거리다가 재밌어 보여서 풀어봤던 문제였다.
구현 문제이기도 했고 문제가 복잡한 것 같아 효율성 따지지 않고 무지성으로 풀었는데, 역시 python3로 제출하니 시간초과가 났고, pypy3로 제출하니 겨우 통과하였다.

무지성 파이썬 코드
import sys
input = sys.stdin.readline
r, c, t = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
clean = []
def out_of_bounds(x, y):
if x < 0 or x >= r or y < 0 or y >= c:
return False
if y == 0 and x in clean:
return False
return True
def spread():
tmp = [[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
for j in range(c):
if arr[i][j] != 0 and arr[i][j] != -1:
cnt = 0
if out_of_bounds(i-1, j):
cnt += 1
tmp[i-1][j] += arr[i][j]//5
if out_of_bounds(i+1, j):
cnt += 1
tmp[i+1][j] += arr[i][j]//5
if out_of_bounds(i, j-1):
cnt += 1
tmp[i][j-1] += arr[i][j]//5
if out_of_bounds(i, j+1):
cnt += 1
tmp[i][j+1] += arr[i][j]//5
tmp[i][j] -= cnt*(arr[i][j]//5)
for i in range(r):
for j in range(c):
arr[i][j] += tmp[i][j]
def wind():
tmp = [[0 for _ in range(c)] for _ in range(r)]
u, d = clean[0], clean[1]
# 위 (반시계)
for i in range(1, c-1):
tmp[u][i+1] = arr[u][i]
arr[u][i] = 0
for i in range(1, u+1):
tmp[u-i][c-1] = arr[u-i+1][c-1]
arr[u - i + 1][c - 1] = 0
for i in range(1, c):
tmp[0][c-i-1] = arr[0][c-i]
arr[0][c - i] = 0
for i in range(1, u+1):
if i != u:
tmp[i][0] = arr[i - 1][0]
arr[i - 1][0] = 0
else:
tmp[i][0] = 0
arr[i - 1][0] = 0
# 아래 (시계)
for i in range(1, c-1):
tmp[d][i+1] = arr[d][i]
arr[d][i] = 0
for i in range(1, r-d):
tmp[d+i][c-1] = arr[d+i-1][c-1]
arr[d + i - 1][c - 1] = 0
for i in range(1, c):
tmp[r-1][c-i-1] = arr[r-1][c-i]
arr[r - 1][c - i] = 0
for i in range(1, r-d):
if i != r-d-1:
tmp[r - 1 - i][0] = arr[r - i][0]
arr[r - i][0] = 0
else:
tmp[r-1-i][0] = 0
arr[r - i][0] = 0
for i in range(r):
for j in range(c):
arr[i][j] += tmp[i][j]
for i in range(r):
if arr[i][0] == -1:
clean.append(i)
for _ in range(t):
spread()
wind()
ans = 0
for i in range(r):
for j in range(c):
ans += arr[i][j]
print(ans+2)
하지만 이렇게 풀어보니 코드의 가독성도 떨어지고 알고리즘이 매우 비효율적이라는 것을 알 수 있다.
문제를 풀면서 생각난 부분인데, 어차피 구하고자 하는 답은 미세먼지의 총 양이고, 공기청정기 바람이 불 때 그 미세먼지들이 어떻게 이동하는지가 중요하기보다는 공기청정기 바로 근처에 있는 미세먼지가 공기청정기 안으로 들어가냐 아니면 안들어가냐 이 부분만 따지면 될 듯 했다.
우선 가독성이 조금 더 좋은 다른 분들의 코드를 참고해보았다.
이 코드 역시 pypy3로 제출해야지만 통과하지만 가독성이 내가 쓴 코드보다 더 읽기 좋았다.
가독성 좋은 코드
import sys
input = sys.stdin.readline
r, c, t = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]
up = -1
down = -1
# 공기 청정기 위치 찾기
for i in range(r):
if arr[i][0] == -1:
up = i
down = i + 1
break
# 미세먼지 확산
def spread():
dx = [-1, 0, 0, 1]
dy = [0, -1, 1, 0]
tmp_arr = [[0] * c for _ in range(r)]
for i in range(r):
for j in range(c):
if arr[i][j] != 0 and arr[i][j] != -1:
tmp = 0
for k in range(4):
nx = dx[k] + i
ny = dy[k] + j
if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
tmp_arr[nx][ny] += arr[i][j] // 5
tmp += arr[i][j] // 5
arr[i][j] -= tmp
for i in range(r):
for j in range(c):
arr[i][j] += tmp_arr[i][j]
# 공기청정기 위쪽 이동
def air_up():
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
direct = 0
before = 0
x, y = up, 1
while True:
nx = x + dx[direct]
ny = y + dy[direct]
if x == up and y == 0:
break
if nx < 0 or nx >= r or ny < 0 or ny >= c:
direct += 1
continue
arr[x][y], before = before, arr[x][y]
x = nx
y = ny
# 공기청정기 아래쪽 이동
def air_down():
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
direct = 0
before = 0
x, y = down, 1
while True:
nx = x + dx[direct]
ny = y + dy[direct]
if x == down and y == 0:
break
if nx < 0 or nx >= r or ny < 0 or ny >= c:
direct += 1
continue
arr[x][y], before = before, arr[x][y]
x = nx
y = ny
for _ in range(t):
spread()
air_up()
air_down()
answer = 0
for i in range(r):
for j in range(c):
if arr[i][j] > 0:
answer += arr[i][j]
print(answer)
'Data Structure & Algorithms' 카테고리의 다른 글
[백준] 12865번: 평범한 배낭 (냅색 알고리즘) (0) | 2022.05.06 |
---|---|
[백준] 1753번: 최단경로 (다익스트라) (0) | 2022.04.23 |
[백준] 1644번: 소수의 연속합 (에라토스테네스의 체, 투 포인터) (0) | 2022.04.15 |
[백준] 10819번: 차이를 최대로 (0) | 2022.04.13 |
[백준] 6588번: 골드바흐의 추측 (에라토스테네스의 체) (0) | 2022.04.04 |