백준(boj) 17144_미세먼지 안녕! (파이썬, c++)

https://www.acmicpc.net/problem/17144

풀이

---

크게 보면 확산, 공기청정기 작동으로 나뉘어진다.

1. 확산

4방향을 확인하며 공기청정기, 범위 밖이 아니면 먼지/5 만큼의 양을 새로운 배열에 추가해주고(중간에 값을 바꿔버리면 안되므로 새로운 배열을 하나 만들어놓고 나중에 처리) , 개수를 세어준다. 4방향을 확인 했으면, 먼지의 양에서 (먼지/5)*퍼진개수를 빼준다.(Arc -= (Arc/5)*cnt)

2. 공기청정기 작동

공기를 한칸씩 이동시킨다. 공기청정기의 윗부분은 RULD방향으로 진행하고, 아랫부분은 RDLU방향으로 진행하므로 벽에 닿으면 방향이 바뀌게, 공기청정기에 닿으면 끝나게 구현해주면 된다.

c++로 구현한 move()함수를 보면, dd를 URDL로 만들어놔서 시작d를 1(R방향)로 놓고, 윗 청정기면 d = (d+3)%4를 해주어서 RULD 순으로 방문하게 만들어 주었고, 아래 청정기는 d = (d+1)%4를 해주어서 RDLU 순으로 방문하게 만들어 주었다

python3(Pypy3 제출)

from sys import*
from collections import*
input = stdin.readline
def play(f):
    temp = 0
    if f == 0:
        nx, ny = clean, 0
    else: nx, ny = clean+1, 0
    for dx, dy in dd[f]:  #f==0위, f==1 아래
        while 1:
            nx, ny = nx + dx, ny + dy
            if nx < 0 or ny < 0 or nx > n - 1 or ny > m - 1:
                nx -= dx;
                ny -= dy;
                break
            if a[nx][ny] == -1: return
            a[nx][ny], temp = temp, a[nx][ny]
​
n,m,t = map(int,input().split())
a=[list(map(int,input().split()))for _ in range(n)]
for i in range(n):
    if a[i][0]==-1:
        clean = i       #[i][0], [i+1][0] 공기청전기
        break
dd=[[(0,1),(-1,0),(0,-1),(1,0)],[(0,1),(1,0),(0,-1),(-1,0)]]  #아래쪽 순환
for _ in range(t):
    check=[[0]*m for _ in range(n)]
    for i in range(n):      #확산
        for j in range(m):
            if a[i][j]==-1: continue
            if a[i][j]:
                cnt=0
                for dx, dy in dd[0]:       #위나 아래 아무거나 가능
                    nx, ny = i+dx, j+dy
                    if nx<0 or ny<0 or nx>n-1 or ny>m-1 or a[nx][ny]==-1: continue
                    cnt+=1
                    check[nx][ny]+=(a[i][j]//5)
                check[i][j] += a[i][j] - ((a[i][j]//5)*cnt)
    a=[x[:] for x in check]
    a[clean][0] = -1
    a[clean+1][0] = -1
    #공기청정기 가동
    play(0)
    play(1)
ans=0
for i in range(n):
    for j in range(m):
        if a[i][j]!=-1: ans+=a[i][j]
print(ans)

C++

#include<cstdio>
#include<memory.h>
#include<vector>
using namespace std;
typedef pair<int, int> P;
const int SIZE = 51;
int R,C,T;
int a[SIZE][SIZE], add[SIZE][SIZE];
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
int exp(int x, int y){
    int cnt=0;
    for(int i=0; i<4; i++){
        int nx, ny;
        nx = x+dx[i], ny = y+dy[i];
        if(nx<0 || ny<0 || nx>R-1 || ny>C-1 || a[nx][ny]==-1) continue;
        cnt++;
        add[nx][ny] += a[x][y]/5;
    }
    return a[x][y] - (a[x][y]/5)*cnt;
}
void move(bool f, int x, int y){
    int d = 1;
    int nx=x, ny=y, prev=0, temp;
    while(1){
        nx += dx[d], ny +=dy[d];
        if(nx<0 || ny<0 || nx>R-1 || ny>C-1){
            nx-=dx[d], ny-=dy[d];
            if(f==false) d=(d+3)%4;
            else if(f==true) d=(d+1)%4;
            continue;
        }
        if(a[nx][ny]==-1) return;        //공기청정기 만나면 끝
        temp = a[nx][ny];
        a[nx][ny] = prev;
        prev = temp;
    }
}
​
int main(){
    vector<P> v;
    scanf("%d %d %d", &R , &C, &T);
    for(int i=0; i<R; i++)
        for(int j=0; j<C; j++){
            scanf("%d", &a[i][j]);
            if(a[i][j]==-1) v.push_back({i, j});
        }
    while(T--){
        memset(add, 0, sizeof(add));
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                a[i][j] = exp(i, j);
            
        for(int i=0; i<R; i++)
            for(int j=0; j<C; j++)
                a[i][j] += add[i][j];
        move(false, v[0].first, v[0].second);
        move(true, v[1].first, v[1].second);
    }
    int res = 0;
    for(int i=0; i<R; i++)
        for(int j=0; j<C; j++){
            if(a[i][j]!=-1) res += a[i][j];
        }
    printf("%d", res);
    return 0;
}

고찰

---

.