728x90
https://www.acmicpc.net/problem/17144
진짜 순수 구현문제다.. 방향벡터를 이용해야하는 정도?만 제외하면..
오랜만에 푸는 문제라 많이 어지러웠지만, 그래도 풀었다..!
문제의 해결방법은 다음과 같다
1. 미세먼지가 확산한다.
2. 공기청정기가 작동한다.
3. 위 과정을 T번 반복한다.
사실 2번은 정말 노가다..라고 할 수 있다. 그냥 값들을 앞으로 옮기기만 하면 되는데, for문이든 while문이든 취향껏 골라서 풀면 된다.
이제 보니 while문써서 인덱스 하나(행 또는 열 값)만을 가지고 푸는 방법이 더 깔끔할 것 같긴 하다.
1번이 살짝 어려울 수 있는데, 어려운 이유는 아마 다음과 같을 것 이다.
미세먼지가 확산을 하는데, 근처 칸에다가 확산된 값을 더해주면 원래 있던 값이 훼손된다 !!
이를 방지하기 위해, 임의의 배열을 하나 만들어서 여기에는 확산된 먼지를 적어주고, tmp에는 확산된 미세먼지의 총량을 기록해주어서
확산이 되고난 후, 확산의 기준점에 tmp 값을 빼줘서 수식을 만족시켜준다. 그리고 마지막으로 원래 배열과 임의의 배열끼리 더해서 확산을 마무리한다!
이 같은 방식이 가능한 이유는, 미세먼지 확산 시에 원래 있던 미세먼지 총량이 커지거나 작아지지 않기 때문이다! (숫자 계산해보면 알게 되실 겁니다)
import sys
from collections import deque
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dx = [0,1,0,-1]
dy = [1,0,-1,0]
def clean():
for i in range(first[0]-1,-1,-1): # ㅜ
if board[i+1][0] == -1: board[i][0]=0
else : board[i+1][0] = board[i][0]
for i in range(1,c): # ㅓ
board[0][i-1] = board[0][i]
for i in range(1,first[0]+1): #ㅗ
board[i-1][c-1] = board[i][c-1]
for i in range(c-1,0,-1): # ㅏ
if board[first[0]][i-1] == -1 : board[first[0]][i]=0
else :board[first[0]][i] = board[first[0]][i-1]
#------
for i in range(second[0]+1,r): #ㅗ
if board[i-1][0] == -1: board[i][0]=0
else : board[i-1][0] = board[i][0]
for i in range(1,c): #ㅓ
board[r-1][i-1] = board[r-1][i]
for i in range(r-1,second[0],-1): #ㅜ
board[i][c-1] = board[i-1][c-1]
for i in range(c-1,0,-1): #ㅏ
if board[second[0]][i-1] == -1 : board[second[0]][i]=0
else : board[second[0]][i] = board[second[0]][i-1]
def bfs():
for _ in range(t):
tmp_arr = [[0] * c for _ in range(r)]
for x in range(r):
for y in range(c):
if board[x][y] > 0:
tmp = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx <0 or ny <0 or nx >= r or ny >= c:
continue
if board[nx][ny] == -1: continue
tmp_arr[nx][ny] += board[x][y] // 5
tmp += board[x][y] // 5
board[x][y] -= tmp
for i in range(r):
for j in range(c):
board[i][j] += tmp_arr[i][j]
clean()
sum = 0
for row in board:
for data in row:
if data != -1:
sum += data
return sum
if __name__ == "__main__":
r,c,t = map(int,input().split())
board = [[0]*c for _ in range(r)]
first = [0,0]
second = [0,0]
for i in range(r):
board[i] = list(map(int,input().split()))
for j in range(len(board[i])):
if board[i][j] == -1:
if first==[0,0]:
first = [i,j]
else: second = [i,j]
print(bfs())
728x90
'알고리즘 > 백준(BOJ)' 카테고리의 다른 글
[백준/파이썬] 12919번 A와 B 2 (0) | 2023.05.27 |
---|---|
[백준/파이썬] 1111번 IQ Test (0) | 2023.05.26 |
[백준/파이썬] 2877번 4와 7 (0) | 2023.04.26 |
[백준/파이썬] 2108번 통계학 (0) | 2023.03.30 |
[백준/파이썬] 2941번 크로아티아 알파벳 (0) | 2023.03.28 |