17144_미세먼지 안녕! (Python)
0. 출처
- 유형 : 구현, 시뮬레이션 (gold 4)
- 링크 : 17144번: 미세먼지 안녕!
1. 기록
- 22/04/02 (토)
2. 풀이
(1) 아이디어, 시간복잡도, 자료구조
1. 아이디어
>> r(행), c(열), t(시간) 입력받고
>> 미세먼지 graph 입력받고
>> 미세먼지 확산 A(r,c)/5
>> 위쪽 공기청정기 위치와 아래쪽 공기청정기 위치를 알아내야 한다.★★
>> 반시계 방향과 시계방향도 코드로 작성해줘야 한다.★★
2. 시간복잡도
3. 자료구조(2) 예제 입력, 예제 출력
- 예제 입력 1 -
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0
- 예제 출력 1 -
188(3) 코드
import sys
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
temp = 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], temp = temp, arr[x][y]
x = nx
y = ny
# 아래쪽 공기청정기 작동
def air_down():
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
direct = 0
temp = 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], temp = temp, 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)(4) 정리
arr[x][y], temp = temp, arr[x][y]위와 같은 코드로
- 현재 칸에 있는 값을 temp 변수에 집어넣고
- 현재 칸 arr[x][y] 에 이전에 있던 칸의 값(temp)을 대입하는 식으로 값의 이동을 구현함을 배웠습니다.
(5) 참고
'코테기록 > 백준' 카테고리의 다른 글
| [백준] 15663_N과 M(9) (Python) (0) | 2022.04.03 |
|---|---|
| [백준] 15657_N과 M(8) (Python) (0) | 2022.04.03 |
| [백준] 15656_N과 M(7) (Python) (0) | 2022.03.31 |
| [백준] 15655_N과 M(6) (Python) (0) | 2022.03.31 |
| [백준] 15654_N과 M(5) (Python) (0) | 2022.03.31 |