파이썬 알고리즘 296번 | [백준 17144번] 미세먼지 안녕 ! - 시뮬레이션, 구현

Yunny.Log ·2023년 1월 24일

Algorithm

목록 보기

300/318

296 미세먼지 안녕~

1) 어떤 전략(알고리즘)으로 해결?

구현, 시뮬레이션 !

2) 코딩 설명

구현 , 시뮬레이션인데 살짝의 bfs를 곁들였던 문제입니다.
까다로운 부분은 배열을 회전시키는 부분에 있다고 생각합니다.

<내 풀이>

저는 배열을 회전시킬 때 행같은 경우는 큐를 사용해서 비교적 쉽게 회전시켰으나 열을 이동시켜야하는 경우를 다루는 것이 상당히 어려웠습니다.
우선 저는 열을 이동시키는 부분은 for문으로 처리해주었습니다.
- 이 과정에서 많은 오류가 발생하였고 범위 설정에 헷갈리기도 했고 체계적이지 못했다고 생각합니다. 다른 분들의 풀이를 참고해 더 효율적이고 깔끔한 풀이를 배워야겠습니다.


import sys
from collections import deque

r,c,t = map(int,sys.stdin.readline().split())
mapp = []
air = []
dust = deque()
dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

for i in range(r) : 
    # 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양
    mapp.append(list(map(int, (sys.stdin.readline().rstrip().split()))))

# 공기청정기 찾기 => a[n][1] a[n+1][1] 의 형태로 저장될 것 
# 미세먼지 찾아서 큐에다가 넣기
for i in range(r) :
    for j in range(c) : 
        if mapp[i][j]==-1 : 
            air.append((i,j)) 
        elif mapp[i][j] > 0 :
            dust.append((i,j,mapp[i][j]))

while t : 
    # 1. 미세먼지의 확산
    now_len_dust = len(dust)
    for i in range(now_len_dust) :
        dr, dc, dq = dust.popleft()
        chk = 0 # 내 먼지를 확산시킨 방향의 갯수
        for j in range(4) :
            tmpr = dr+dirr[j] 
            tmpc = dc+dirc[j]
            # 범위 안 벗어나고 공기청정기가 아니라면 확산시키기
            if 0<=tmpr<r and 0<=tmpc<c and mapp[tmpr][tmpc]!=-1 :
                mapp[tmpr][tmpc]+= dq//5 
                chk+=1
        mapp[dr][dc]-=((dq//5) * chk)

    # 2. 공기청정기 작동

    # 2-1 : 반시계
    ar,ac = air[0]

    # 2-1-1
    q =deque(mapp[ar])
    q.appendleft(-1)
    q[1] = 0
    tmp1 = q[-1]
    q.pop()
    mapp[ar] = list(q)

    # 2-1-2 
    for i in range(ar-1,0,-1) :
        tmp2 = mapp[i][c-1]
        mapp[i][c-1] = tmp1
        tmp1 = tmp2
    
    # 2-1-3
    q =deque(mapp[0]) 
    q.append(tmp1)
    tmp1 = q.popleft()   
    mapp[0] = list(q)

    # 2-1-4
    for i in range(1, ar) :
        tmp2 = mapp[i][0]
        mapp[i][0] = tmp1
        tmp1= tmp2

    mapp[ar][ac] = -1
    
    # 2-2 : 시계
    ar,ac = air[1]

    # 2-2-1
    q = deque(mapp[ar])
    q.appendleft(-1)
    q[1] = 0
    tmp1 = q[-1]
    q.pop()
    mapp[ar] = list(q)

    # 2-2-2 
    for i in range(ar+1,r-1) :
        tmp2 = mapp[i][c-1]
        mapp[i][c-1] = tmp1
        tmp1 = tmp2

    # 2-2-3
    q =deque(mapp[r-1]) 
    q.append(tmp1)
    tmp1 = q.popleft()   
    mapp[r-1] = list(q)

    # 2-2-4
    for i in range(r-2,ar,-1) : # 처음에 이 범위 잘못 설정했었음
        tmp2 = mapp[i][0]
        mapp[i][0] = tmp1
        tmp1= tmp2

    mapp[ar][ac] = -1
    
    # 다시 미세먼지 존재 공간 검사
    for i in range(r) :
        for j in range(c) : 
            if mapp[i][j] > 0 :
                dust.append((i,j,mapp[i][j]))

    t-=1
    
# 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.
dust = 0
for i in range(r) :
    for j in range(c) : 
        if mapp[i][j] > 0 : 
            dust+=mapp[i][j]

print(dust)

< 내 틀렸던 풀이, 문제점>

1트

미세먼지 확산은 ok 입니다. (사실 추후 보니 이것도 안 ok였습니다..)
그러나~ 공기청정기가 처리해주는 로직이 틀렸습니다 !
왜냐면 저는 그냥 이전거를 지금거로 덮어써주는 단순한 방식으로 생각했는데 그러면 값이 덮어씌워지게 되는 problem이 발생하게 됩니다.


import sys
from collections import deque

r,c,t = map(int,sys.stdin.readline().split())
mapp = []
air = []
dust = deque()
dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

for i in range(r) : 
    # 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양
    mapp.append(list(map(int, (sys.stdin.readline().rstrip().split()))))

# 공기청정기 찾기 => a[n][1] a[n+1][1] 의 형태로 저장될 것 
# 미세먼지 찾아서 큐에다가 넣기
for i in range(r) :
    for j in range(c) : 
        if mapp[i][j]==-1 : 
            air.append((i,j)) 
        elif mapp[i][j] > 0 :
            dust.append((i,j,mapp[i][j]))

while t : 
    # 1. 미세먼지의 확산
    print("time : " , t )
    for i in range(len(dust)) :
        dr, dc, dq = dust.popleft()
        chk = 0 # 내 먼지를 확산시킨 방향의 갯수
        for j in range(4) :
            tmpr = dr+dirr[j] 
            tmpc = dc+dirc[j]
            # 범위 안 벗어나고 공기청정기가 아니라면 확산시키기
            if 0<=tmpr<r and 0<=tmpc<c and mapp[tmpr][tmpc]!=-1 :
                mapp[tmpr][tmpc]+= dq//5 
                chk+=1
        mapp[dr][dc]-=(dq//5) * chk
    print("\n hi1")
    for i in range(r) :
        print(mapp[i])
    print("\n")
    # 2. 공기청정기 작동

    # 2-1 : 반시계
    ar,ac = air[0]
    for i in range(2,c-1) : 
        tmp = mapp[ar][i]
        mapp[ar][i] = mapp[ar][i-1]
    for i in range(ar,0,-1) :
        mapp[i-1][c-1] = mapp[i][c-1]
    for i in range(c-1,0,-1) :
        mapp[0][i-1] = mapp[0][i]
    for i in range(0,ar-1) :
        mapp[i+1][0] = mapp[i][0]
    mapp[ar][ac] = -1

    # 2-2 : 시계
    ar,ac = air[1]
    for i in range(1,c-1) : 
        mapp[ar][i+1] = mapp[ar][i]
    for i in range(ar,r-1) :
        mapp[i+1][c-1] = mapp[i][c-1]
    for i in range(c-1,0,-1) :
        mapp[r-1][i-1] = mapp[r-1][i]
    for i in range(r-1,ar,-1) :
        mapp[i-1][0] = mapp[i][0]
    mapp[ar][ac] = -1
    print("\n hi2")
    for i in range(r) :
        print(mapp[i])
    print("\n")
    # 다시 미세먼지 존재 공간 검사
    for i in range(r) :
        for j in range(c) : 
            if mapp[i][j] > 0 :
                dust.append((i,j,mapp[i][j]))

    t-=1

# 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

dust = 0

for i in range(r) :
    for j in range(c) : 
        if mapp[i][j] > 0 : 
            dust+=1

print(dust)

2트

이제 공기청정기가 도는 것은 정상적으로 됩니다. (각 시계, 반시계)
시계, 반시계 방향으로 돌리는 것은 행이 왼쪽, 오른쪽으로 이동하는 것은 큐로 구현했고! 위, 아래~ 로 움직이는 것은

2트 full code

import sys
from collections import deque

r,c,t = map(int,sys.stdin.readline().split())
mapp = []
air = []
dust = deque()
dirr = [-1,1,0,0]
dirc = [0,0,-1,1]

for i in range(r) : 
    # 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양
    mapp.append(list(map(int, (sys.stdin.readline().rstrip().split()))))

# 공기청정기 찾기 => a[n][1] a[n+1][1] 의 형태로 저장될 것 
# 미세먼지 찾아서 큐에다가 넣기
for i in range(r) :
    for j in range(c) : 
        if mapp[i][j]==-1 : 
            air.append((i,j)) 
        elif mapp[i][j] > 0 :
            dust.append((i,j,mapp[i][j]))

while t : 
    # 1. 미세먼지의 확산
    for i in range(len(dust)) :
        dr, dc, dq = dust.popleft()
        chk = 0 # 내 먼지를 확산시킨 방향의 갯수
        for j in range(4) :
            tmpr = dr+dirr[j] 
            tmpc = dc+dirc[j]
            # 범위 안 벗어나고 공기청정기가 아니라면 확산시키기
            if 0<=tmpr<r and 0<=tmpc<c and mapp[tmpr][tmpc]!=-1 :
                mapp[tmpr][tmpc]+= dq//5 
                chk+=1
        mapp[dr][dc]-=(dq//5) * chk

    print("\n미세먼지 확산  ")    
    for i in range(r) :
        print(mapp[i])
    print("\n")
    # 2. 공기청정기 작동

    # 2-1 : 반시계
    ar,ac = air[0]

    # 2-1-1
    q =deque(mapp[ar])
    q.appendleft(-1)
    q[1] = 0
    tmp1 = q[-1]
    q.pop()
    mapp[ar] = list(q)

    # 2-1-2 
    for i in range(ar-1,0,-1) :
        tmp2 = mapp[i][c-1]
        mapp[i][c-1] = tmp1
        tmp1 = tmp2
    
    # 2-1-3
    q =deque(mapp[0]) 
    q.append(tmp1)
    tmp1 = q.popleft()   
    mapp[0] = list(q)

    # 2-1-4
    for i in range(1, ar) :
        tmp2 = mapp[i][0]
        mapp[i][0] = tmp1
        tmp1= tmp2

    mapp[ar][ac] = -1
    
    # 2-2 : 시계
    ar,ac = air[1]

    # 2-2-1
    q = deque(mapp[ar])
    q.appendleft(-1)
    q[1] = 0
    tmp1 = q[-1]
    q.pop()
    mapp[ar] = list(q)

    # 2-2-2 
    for i in range(ar+1,r-1) :
        tmp2 = mapp[i][c-1]
        mapp[i][c-1] = tmp1
        tmp1 = tmp2

    # 2-2-3
    q =deque(mapp[r-1]) 
    q.append(tmp1)
    tmp1 = q.popleft()   
    mapp[r-1] = list(q)

    # 2-2-4
    for i in range(r-1,ar) :
        tmp2 = mapp[i][0]
        mapp[i][0] = tmp1
        tmp1= tmp2

    mapp[ar][ac] = -1
    
    # 다시 미세먼지 존재 공간 검사
    for i in range(r) :
        for j in range(c) : 
            if mapp[i][j] > 0 :
                dust.append((i,j,mapp[i][j]))

    t-=1

# 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다.

dust = 0

print("\n\n")
for i in range(r) :
    for j in range(c) : 
        if mapp[i][j] > 0 : 
            dust+=mapp[i][j]

print(dust)

질문글 참고

https://www.acmicpc.net/board/view/79189

안녕하세요, 위 코드는 첫번째 테스트케이스의 정답이 우연히 맞지만, 먼지의 확산이 잘못된 것으로 보입니다.
별도의 map 배열을 하나 더 만들지 않고 기존 map 배열에 바로 확산을 시키면 그 값들이 주변에 더해지면서 원본이 손상됩니다.
dust 에 저장된 인덱스들을 순차적으로 접근하더라도 이미 그 값이 손상된 값이기 때문에 잘못된 값을 확산시키게 됩니다.
별도의 map 을 하나 더 만들거나 pos class 에 원본 미세먼지 양을 같이 저장하면 될 것 같습니다.

정답 코드의 회전 후 결과

[0, 0, 0, 0, 0, 1, 8, 6]  
[0, 0, 1, 0, 3, 0, 5, 5]  
[-1, 0, 2, 1, 1, 0, 4, 6] 
[-1, 0, 5, 2, 0, 0, 2, 12]
[0, 1, 1, 0, 5, 10, 13, 0]
[0, 1, 9, 4, 3, 5, 12, 8] 
[8, 17, 8, 3, 4, 8, 4, 0] 




[0, 0, 0, 0, 2, 7, 6, 5]  
[0, 0, 1, 0, 3, 1, 3, 6]  
[-1, 0, 0, 3, 1, 1, 0, 6] 
[-1, 0, 1, 1, 3, 1, 2, 6] 
[1, 1, 3, 1, 3, 6, 9, 7]  
[9, 5, 6, 5, 5, 6, 8, 5]  
[10, 9, 4, 5, 6, 7, 1, 7]

내 코드의 회전 후 결과

[0, 0, 0, 0, 0, 1, 8, 6]
[0, 0, 1, 0, 3, 0, 5, 5]
[-1, 0, 2, 1, 1, 0, 4, 6]
[-1, 0, 5, 2, 0, 0, 2, 12]
[0, 1, 1, 0, 5, 10, 13, 0]
[0, 1, 9, 4, 3, 5, 12, 8]
[8, 17, 8, 3, 4, 8, 4, 0]






        [0, 0, 0, 0, 2, 7, 6, 5]
        [0, 0, 1, 0, 3, 1, 3, 6]
        [-1, 0, 0, 3, 1, 1, 0, 6]
        [-1, 0, 1, 1, 3, 1, 2, 6]
        [0, 1, 3, 1, 3, 6, 9, 7]
# 여기가 [1, 5, 6, 5, 5, 6, 8, 5]
다르다   [10, 9, 4, 5, 6, 7, 1, 7]

=> 하핫 지금 보니깐 시계 방향의 마지막 화살표 부분이 다르다..

<반성 점>

시계 방향 처리 구현 코드

2-2-1 ➡
2-2-2 ⬇
2-2-3 ⬅
2-2-4 ⬆

    
    # 2-2 : 시계
    ar,ac = air[1] 

    # 2-2-1
    q = deque(mapp[ar])
    q.appendleft(-1)
    q[1] = 0
    tmp1 = q[-1]
    q.pop()
    mapp[ar] = list(q)

    # 2-2-2 
    for i in range(ar+1,r-1) :
        tmp2 = mapp[i][c-1]
        mapp[i][c-1] = tmp1
        tmp1 = tmp2

    # 2-2-3
    q =deque(mapp[r-1]) 
    q.append(tmp1)
    tmp1 = q.popleft()   
    mapp[r-1] = list(q)

    # 2-2-4 - 틀린 버전
    # for i in range(r-1,ar) :
    #     tmp2 = mapp[i][0]
    #     mapp[i][0] = tmp1
    #     tmp1= tmp2
        
    # 2-2-4
    for i in range(r-2,ar,-1) :
        tmp2 = mapp[i][0]
        mapp[i][0] = tmp1
        tmp1= tmp2

    mapp[ar][ac] = -1