[백준 17144번] 미세먼지 안녕!(파이썬)

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

17144번: 미세먼지 안녕!

 

미세먼지를 공기청정기로

돌려주는 것이 까다로웠던 문항.

 

이 알고리즘에서 구현해야할 것은 2가지입니다.

 

1. 미세먼지 분배

 

2. 공기청정기 바람

 

 

미세먼지 분배부터 보겠습니다.

문제에서 '동시에'분배된다

라는 것에 유의하셔야합니다.

'동시에 분배한다'라고 나오시면

별도의 리스트를 만든 후

분배를 하시는 걸 권장드립니다.

 

제가 처음 알고리즘 문제를 풀 때

흔히했던 실수입니다.

동시에 퍼진다고 했는데

NG의 경우로 구하면

이미 분배된 걸 다시 분배하는 실수를 범할 수 있습니다.

 

2. 공기청정기 이동

이 문제에서 가장 까다로운 부분이었습니다.

공기의 바람이 계속 이동하는 개념입니다.

바로 오른쪽 칸에 0을 대입하고

계속 이동하면서

0과 교체하는 식으로 코드를 구성할 수 있습니다.

 

#백준 17144번 미세먼지 안녕!
from copy import deepcopy

R,C,T=map(int,input().split())

graph=[]
vacum=[]

dx=[0,-1,0,1]
dy=[1,0,-1,0]

for i in range(R):
    data=list(map(int,input().split()))
    for j in range(C):
        if data[j]==-1:
            vacum.append([i,j])
    graph.append(data)

for _ in range(T):
    #1.미세먼지가 서로 확산한다
    temp=[[0]*C for _ in range(R)]
    for v in vacum:
        vx,vy=v
        temp[vx][vy]=-1

    for x in range(R):
        for y in range(C):
            if graph[x][y]>0:
                dust=graph[x][y]
                tmp=0
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]
                    if nx<0 or nx>=R or ny<0 or ny>=C:
                        continue
                    if graph[nx][ny]==-1:
                        continue

                    temp[nx][ny]+=dust//5
                    tmp+=dust//5
                temp[x][y]+=dust-tmp

    graph=deepcopy(temp)
    #2.진공청소기가 위로 도는 거, 아래로 도는 거 2개임
    #먼저 위가 도는 거
    x,y=vacum[0]
    y+=1
    vx=vacum[0][0]
    up_x=[0,-1,0,1]
    up_y=[1,0,-1,0]
    direct=0
    before=0
    while True:
        nx=x+up_x[direct]
        ny=y+up_y[direct]

        if x==vx and y==0:
            break
        if nx<0 or nx>=R or ny<0 or ny>=C:
            direct=(direct+1)%4
            continue
        graph[x][y],before=before,graph[x][y]
        x=nx
        y=ny
    #아래꺼
    x,y=vacum[1]
    vx=vacum[1][0]
    y+=1
    down_x=[0,1,0,-1]
    down_y=[1,0,-1,0]
    direct=0
    before=0
    while True:
        nx=x+down_x[direct]
        ny=y+down_y[direct]

        if x==vx and y==0:
            break
        if nx<0 or nx>=R or ny<0 or ny>=C:
            direct=(direct+1)%4
            continue
        graph[x][y],before=before,graph[x][y]
        x=nx
        y=ny

answer=0
for x in range(R):
    for y in range(C):
        if graph[x][y]>0:
            answer+=graph[x][y]

print(answer)

https://kyun2da.github.io/2021/04/20/brownsmog/

[백준 / Python] 17144 미세먼지 안녕! - Kyun2da Blog

https://pacific-ocean.tistory.com/378

[백준] 17144번(python 파이썬)

 

이 문항같은 경우에는

리스트를 swap하는 것에 대한

개념을 일꺠울 수 있는 문제입니다.

이 문제 하나로

어떻게 배열의 요소를 바꿔줄 지

고민해볼 수 있습니다.

 

(추가업데이트:2022.10.14)

from copy import deepcopy
R,C,T=map(int,input().split())

dx=[-1,0,1,0]
dy=[0,1,0,-1]

room=[]
air=[]
for i in range(R):
    tmp=list(map(int,input().split()))
    room.append(tmp)
    for j in range(C):
        if tmp[j]==-1:
            air.append((i,j))
def inside(x,y):
    if x<0 or x>=R or y<0 or y>=C:
        return False
    return True

def spread():
    global room
    temp=[[0]*C for _ in range(R)]
    for x in range(R):
        for y in range(C):
            #먼지가 있는 지점에서 먼지를 분비해준다
            if room[x][y]>0:
                now=room[x][y]
                point=0
                sp=set()
                for d in range(4):
                    nx=x+dx[d]
                    ny=y+dy[d]

                    if not inside(nx,ny):
                        continue

                    if room[nx][ny]==-1:
                        continue
                    point+=1
                    sp.add(d)

                go=now//5

                for s in sp:
                    nx=x+dx[s]
                    ny=y+dy[s]

                    temp[nx][ny]+=go

                temp[x][y]+=now-go*point
    room=deepcopy(temp)
    for ax,ay in air:
        room[ax][ay]=-1

def clean():
    #공기청정기 위-->바로 위칸을 0으로 두고 하나씩 밀기
    #공기청정기 아래-->바로 아래칸을 0으로 두고 하나씩 밀기

    #위
    ux,uy=air[0]
    x,y=ux-1,uy
    room[x][y]=0
    px,py=x,y
    d=0
    while True:

        x+=dx[d]
        y+=dy[d]
        if x==ux and y==uy:
            break
        if not inside(x,y):
            x-=dx[d]
            y-=dy[d]
            d=(d+1)%4
            continue
        if x>ux:
            x-=dx[d]
            y-=dy[d]
            d=(d+1)%4
            continue

        room[x][y],room[px][py]=room[px][py],room[x][y]
        px,py=x,y
        # for k in range(R):
        #     print(room[k])
        # print()

    #아래
    bx,by=air[1]
    x,y=bx+1,by
    room[x][y] = 0
    px, py = x, y
    d = 2
    while True:

        x += dx[d]
        y += dy[d]
        # print(x,y)
        if x == bx and y == by:
            break
        if not inside(x, y):
            x -= dx[d]
            y -= dy[d]
            d = (d -1) % 4
            continue
        if x<bx:
            x-=dx[d]
            y-=dy[d]
            d=(d-1)%4
            continue

        room[x][y], room[px][py] = room[px][py], room[x][y]
        px, py = x, y
        # for k in range(R):
        #     print(room[k])
        # print()


for time in range(1,T+1):
    #1. 확신
    spread()

    #2공기청정
    clean()
    # for x in range(R):
    #     print(room[x])
    # print()
#공기청정기는 -1로 표시해줘서, 2로 초기화해야 공기청정기를 다 더해도 공기청정기 합한 게 상쇄
answer=2
for k in range(R):
    answer+=sum(room[k])

print(answer)

좀 더 보기 좋게 바꿔본 코드.

 

swap하는 걸 좀더 깔끔하게 바꿔봤습니다.

 

이 문제에서 주의할 점은

분배할 때 

'해당 지점에 ...의 공기가 남아있다'라는 부분.

해당 지점에서 공기를 분배한 다음에

현 시점은 temp[x][y]+=넣어줄거

이렇게 구현해야 맞습니다.

만약 temp[x][y]=넣어줄거

이렇게 구현해버리면

이전에 다른 것이 이 지역에 들어와도 반영이 되지 않아 틀립니다.