[코테준비] 8. 백준- 미세먼지 안녕! (17144) python "삼성 SW 역량 테스트 기출 문제" -작성중

미세먼지 안녕!

• 링크:https://www.acmicpc.net/problem/17144
• 난이도:골드 4
• 분류: 구현, 시뮬레이션
• 직접 푼 여부: O 그런데 numpy를 써야하는 것이라 다시 코드 짬

풀이 노트

일단, 생각과정은 아래와 같다. 

여기서 공기청정기 (aka 공청기 from now on)로 인한 공기의 확산이 일어날 때, 1)slicing해서 통으로 옮길것이냐, 2)한칸씩 옮길 것이냐 골라야했고, 아무생각없이 1번을 했다.

 

그 코드는 아래와 같고 실패했다. 이유는 2차원 배열 슬라이싱은 내가 쓴대로 하면 아무 의미가 없었기 때문(=틀린방법!)이다. (그래서 그냥 리스트 상에서 슬라이싱하려면 https://programming119.tistory.com/169 이방법을 써야하는데, 이렇게 하면 너무 비효율적일 것 같기에 2번방법으로 했다. 사실 시간복잡도는 안넘을 것 같다)  numpy에 너무 익숙해져버렸던 걸까. 그래서 numpy로 고쳐서 했더니 정답이다. 하지만, numpy는 기본 라이브러리가 아니기에, 백준에서 런타임에러가 난다. 당연히 삼성코테에서도 numpy를 사용할 수 없다. 그래서 2번 방법으로 구현하는 방법을 다시 코드로 짰고, 그것은 통과되었다! (제일 아래 정답코드 공개)

틀린 풀이 ❌

# 17144 미세먼지 안녕!

import sys
from copy import deepcopy
sys.stdin = open("./input.txt")
input = sys.stdin.readline

#input
r,c,t= map(int, input().split())
a=[list(map(int, input().split())) for _ in range(r)]

# 공기청정기 위치 찾기
top, bottom =0,0
for i in range(r):
    if -1 in a[i]:
        top, bottom =i, i+1
        break
# 기본준비
dc =[-1,0,1,0]
dr =[0,-1,0,1]

# 미세먼지 확산 & 공청기 작동
for time in range(t):
    #1. 미세먼지 확산
    tempa = deepcopy(a)
    for rr in range(r):
        for cc in range(c):
            if tempa[rr][cc]>0:
                # 값이 있을 때만 확산
                cnt =0
                spread = tempa[rr][cc]//5
                for i in range(4):
                    newrr = rr+dr[i]
                    newcc = cc + dc[i]
                    # print(newrr, newcc)
                    # print()
                    if (0<=newrr<r) and (0<=newcc<c) and (tempa[newrr][newcc]!=-1):
                        # not(newcc==0 and newrr in air) 가능
                        # 범위가 벗어나면 안되고, 공청기 있는 곳도 안됨
                        cnt+=1
                        a[newrr][newcc] +=spread #원래 있던 먼지에 새로운 먼지 추가
                # 확산되면 원래 위치 먼지 적어짐
                a[rr][cc] -= spread*cnt
    print(a)
    # 2. 공기청정기
    tempa = deepcopy(a)
    # 위쪽
    a[top][1:] =[0] + tempa[top][1:-1]  # 좌 (0)
    print(top)
    print(a[:top])
    print(a[:top][-1])
    print(tempa[1:top+1][-1])
    a[:top][-1] = tempa[1:top+1][-1]  # 상 (위에서부터 순서임)
    a[0][:-1]=tempa[0][1:] # 우
    a[1:top][0] = tempa[0][0:top+1]# 하
    # 아래쪽
    a[bottom][1:] = [0] + tempa[bottom][1:-1] #좌 (0)
    a[bottom+1:][-1] = tempa[bottom:-1][-1]#하
    a[-1][:-1] = tempa[-1][1:]#우
    a[bottom+1:-1][0] = tempa[bottom+2:][0]#상
    print(a)

# 남은 미세먼지 세기
ans=2 # 다sum할거라 공청기로 인한 -2 미리 처리
for i in range(r):
    ans+=sum(a[i][:])
print(ans)

 

맞지만 numpy를 쓰는 풀이

# 17144 미세먼지 안녕!

import sys
from copy import deepcopy
import numpy as np
input = sys.stdin.readline

#input
r,c,t= map(int, input().split())
la=[list(map(int, input().split())) for _ in range(r)]
a=np.array(la)
# 공기청정기 위치 찾기
top, bottom =0,0
for i in range(r):
    if -1 in a[i]:
        top, bottom =i, i+1
        break
# 기본준비
dc =[-1,0,1,0]
dr =[0,-1,0,1]

# 미세먼지 확산 & 공청기 작동
for time in range(t):
    #1. 미세먼지 확산
    tempa = deepcopy(a)
    for rr in range(r):
        for cc in range(c):
            if tempa[rr,cc]>0:
                # 값이 있을 때만 확산
                cnt =0
                spread = tempa[rr,cc]//5
                for i in range(4):
                    newrr = rr+dr[i]
                    newcc = cc + dc[i]
                    # print(newrr, newcc)
                    # print()
                    if (0<=newrr<r) and (0<=newcc<c) and (tempa[newrr,newcc]!=-1):
                        # not(newcc==0 and newrr in air) 가능
                        # 범위가 벗어나면 안되고, 공청기 있는 곳도 안됨
                        cnt+=1
                        a[newrr,newcc] +=spread #원래 있던 먼지에 새로운 먼지 추가
                # 확산되면 원래 위치 먼지 적어짐
                a[rr,cc] -= spread*cnt
   

# 남은 미세먼지 세기
ans=2 # 다sum할거라 공청기로 인한 -2 미리 처리
for i in range(r):
    ans+=sum(a[i,:])
print(ans)

백준은 numpy를 취급하지 않아서 에러가 난다.

---

정답 풀이 💻