[Python] 백준 미세먼지 안녕!

1. 문제 - 백준 미세먼지 안녕! (삼성 SW 역량테스트 기출)

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

 

✅ 풀이

answer = 0

r, c, t = map(int, input().split())
machine = []
board = []
for i in range(r):
  board.append(list(map(int, input().split())))
  for j in range(c):
    if board[i][j] == -1:		# 공기청정기의 위치 저장
      machine.append((i, j))

def spread():

def purifying():
            
for _ in range(t):    # t초만큼 반복
  spread()
  purifying()

for i in range(r):    # 남은 미세먼지의 총합 구하기
  for j in range(c):
    if board[i][j] > 0:
      answer += board[i][j]
      
print(answer)

 

일단 큰 틀은 이렇다. 문제 조건에 의하면, 1초마다 아래와 같은 사항이 반복된다.

- 미세먼지가 확산된다 ==> spread() 함수화

- 공기청정기가 작동한다 ==> purifying() 함수화

 

t초 후에 남아있는 미세먼지의 총합을 출력하는 것이 목적이므로, 위 함수를 차례대로 t초간 수행한 후의 총합을 출력한다.

 

1) spread() 함수 맞왜틀 ?

- 미세 먼지가 있는 모든 칸에서 동시에 일어나며, 경계를 벗어나거나 공기청정기가 있는 곳에는 확산되지 않는다.

- 인접한 확산되는 양은 A(r, c) // 5 이며 (소수점을 버리므로), 기존 미세먼지의 양은 A(r,c) - A(r, c) // 5 * 확산된 칸의 갯수

 

❌ 틀린 풀이

def spread():
  pos = []
  
  for x in range(r):
    for y in range(c):
      if board[x][y] > 0:
        pos.append((x, y))
        
  for x, y in pos:
    count = 0    # 확산되는 양
    for dir in range(4):
      nx = x + dx[dir]
      ny = y + dy[dir]

      if 0<=nx<r and 0<=ny<c and board[nx][ny] >= 0:
        board[nx][ny] += int(board[x][y] / 5)
        count += int(board[x][y] / 5)

    board[x][y] -= count

- 이 코드는 확산의 결과를 바로 원본 board에 반영하므로, 원래 공기청정기의 위치가 아닌 곳에서도 먼지의 확산이 일어날 수 있다.

(예를들어 [[5, 0], [0, 0]] 이라고 하면 확산 후 --> [[3, 1], [1, 0]] --> 원래 공기청정기의 위치가 아니었던 1 위치에서도 확산 발생)

- 따라서 기존 먼지의 위치 기준으로 확산의 결과를 별도의 배열에 저장한 다음, 한꺼번에 반영해야한다.

 

✅ 맞는 풀이

def spread():
  temp = [[0] * c for _ in range(r)]
  
  for x in range(r):
    for y in range(c):
      if board[x][y] > 0:   # 미세먼지가 있는곳
        count = 0    # 확산된 갯수
        amount = board[x][y] // 5
        for dir in range(4):
          nx = x + dx[dir]
          ny = y + dy[dir]

          # 칸이 없거나 (경계를 벗어나거나), 인접한 방향에 공기청정기가 있다면 확산이 일어나지 않는다.
          if 0<=nx<r and 0<=ny<c and board[nx][ny] != -1:
            temp[nx][ny] += amount
            count += 1

        board[x][y] -= amount * count
        # 먼저 원래 미세먼지의 값을 업데이트해도 이후 미세먼지가 있는 곳에 영향을 주지 않는다. 
        # (최대 퍼질 수 있는 곳이 4곳이기 때문이기 때문에, board[x][y]가 0이 될 수 없음)

  for i in range(r):
    for j in range(c):
      board[i][j] += temp[i][j]

 

- 먼저 미세먼지가 있는곳마다 주변에 확산되는 먼지의 양을 board가 아닌 임의의 배열인 temp 배열에 업데이트시킨다.

- 그런 다음, 한꺼번에 원본 board에 확산된 먼지의 양을 더해준다.

 

2) purifying()

- 공기청정기는  항상 1열에 위치하며, 두행을 차지한다. 

- 위쪽에서는 반시계 방향으로 먼지를 한칸 밀어내며, 아래쪽에서는 시계 방향으로 먼지를 한칸 밀어낸다. 

==> 이부분에서 막혔다.. 여러 풀이가 존재해서 각각 뜯어보고자 한다.

 

✅ 풀이

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

def purifying():
  # 위쪽
  # 동쪽부터시작하니 d=0
  d = 0
  before = 0  # 바람으로 밀어내기 전에 이전값을 저장할 변수, 공기청정기에서부터 밀어내니까 처음에는 0임
  #공기청정기 시작부분 다음칸부터 시작
  x, y = machine[0][0],machine[0][1]+1
  
  while True:
    # 공기청정기를 만나면 멈춤
    if x == machine[0][0] and y == machine[0][1]:
      break
      
    nx = x+dx[d]
    ny = y+dy[d]

    # 그 다음 위치가 바람이 벽을만나면 방향을 꺾음
    if nx == r or ny == c or nx == -1 or ny == -1:
      d -= 1
      continue
    
    board[x][y], before = before, board[x][y]   # 바람으로 밀어내고 (교환하고)
    x,y = nx,ny   # 방향 갱신

  # 아래쪽
  d=0
  before=0
  
  x,y = machine[1][0],machine[1][1]+1
  
  while True:
    if x == machine[1][0] and y ==machine[1][1]:
      break
      
    nx = x+dx[d]
    ny = y+dy[d]

    #바람이 벽을만나면 방향을 꺾음
    if nx == r or ny == c or nx == -1 or ny == -1:
      d += 1
      continue
    board[x][y],before = before,board[x][y]
    x,y=nx,ny

 

- dx, dy 오프셋 배열 (인접한 칸으로 이동할 방향 배열)을 시계방향 기준인 동 -> 남 -> 서 -> 북 순서대로 만든다.

- 따라서 벽을 만날때는 공기청정기의 위쪽에서는 dx, dy 오프셋 배열의 인덱스가 0 -> 1 -> 2 -> 3 이 될 것이고 (시계 방향)

공기청정기의 아래쪽에서는 인덱스가 0 -> -1 -> -2 -> -3 이 될 것이다. (반시계방향)

- 그리고 반복문을 통해 회전하면서 공기청정기를 만나기 전까지, 기존 미세먼지들을 한칸씩 방향대로 밀어낸다.