7/26 Coding Test

✅ BOJ Implementation

🎈 17144 미세먼지 안녕!

보드판의 크기는 r행 c열로 구성되어 있다. 공기청정기는 항상 1번 열에 있으며 크기는 2행을 차지한다. 공기청정기가 설치되어 있지 않은 칸에는 미세먼지가 존재하고, (r,c)에 있는 미세먼지의 양은 A(r,c)이다. 1초 동안 아래 적힌 일이 순서대로 일어난다.

• 미세먼지가 확산되고 확산은 미세먼지가 있는 모든 칸에서 동시에 발생
• 인접한 4 방향으로 확산되고 인접한 방향에 공기청정기가 있거나, 칸이 없으면 그 방향으로는 확산 X
• 확산되는 양은 A(r,c)/5 (소수점 생략), r행 c열에 남은 미세먼지 양은 A-A/5*확산된 칸 수
• 공기청정기가 작동해 위쪽 공기청정기는 반시계방향, 아래쪽 공기청정기는 시계방향으로 순환.
• 바람이 불면 미세먼지가 바랑 방향대로 한 칸씩 이동
• 공기청정기로 들어간 바람은 모두 정화

확산과, 공기청정기 방향 순환 결과 예시는 아래와 같다.

• 입력값 : 첫 줄에 R,C,T 둘째 줄부터 R줄에 걸쳐 보드판 배열이 주어짐. 공기청정기 설치된 곳은 -1로 표기되고 가운데 칸에만 존재(위 아래 2칸 이상 여유 존재), 나머지 값은 미세먼지 양
• 출력값 : 보드판 배열 내 공기청정기 제외한 먼지양 합산

import sys
input = sys.stdin.readline

r, c, t = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(r)]
# 공기청정기 위치 확인
for i in range(r):
    if board[i][0] == -1:
        up = i
        down = i+1
        break

def diffusion():
    dx, dy = (-1, 1, 0, 0), (0, 0, -1, 1)
    dif = [[0]*c for _ in range(r)]
    for x in range(r):
        for y in range(c):
            if board[x][y] == 0 or board[x][y] == -1:
                continue
            dust = board[x][y] // 5
            cnt = 0
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if 0<=nx<r and 0<=ny<c and board[nx][ny] != -1:
                    dif[nx][ny] += dust
                    cnt += 1
            dif[x][y] -= dust * cnt
    for i in range(r):
        for j in range(c):
            board[i][j] += dif[i][j]

def air_upside():
    # 동북서남 반시계
    dx, dy = (0, -1, 0, 1), (1, 0, -1, 0)
    x, y = up, 1
    dir = 0
    prev = 0
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        if x == up and y == 0:
            break
        if not 0<=nx<r or not 0<=ny<c:
            dir += 1
            continue
        board[x][y], prev = prev, board[x][y]
        x, y = nx, ny

def air_downside():
    # 시계방향 동남서북
    dx, dy = (0, 1, 0, -1), (1, 0, -1, 0)
    x, y = down, 1
    dir = 0
    prev = 0
    while True:
        nx = x + dx[dir]
        ny = y + dy[dir]
        if x == down and y == 0:
            break
        if not 0<=nx<r or not 0<=ny<c:
            dir += 1
            continue
        board[x][y], prev = prev, board[x][y]
        x, y = nx, ny
for _ in range(t):
    diffusion()
    air_upside()
    air_downside()
print(sum(map(sum, board)) + 2)

< 풀이 과정 >

상당히 딥한 구현 문제.
풀이 과정은 크게 4가지로 나뉜다. 입력값 지정, 공기 청정기 위치 지정, 확산 시 보드 판 내 값 변경, 공기청정기 위아래 방향 이동

• 1. 입력값을 처리한 후 공기청정기 위치(행)를 up, down 두 변수에 저장.
• 2-1. 확산 시 함수 생성해주는데, 확산 시 값들을 저장해줄 0으로된 2차원 배열을 미리 만든다.
• 2-2. 이후 dust로 현 위치의 값을 5로 나누어준 몫을 저장하고 cnt를 0으로 둔 후 4방향의 거쳐 확산 가능한 지역에 퍼진 횟수 만큼 dust를 더해주기도, 현 위치에서 cnt 수만큼 dust를 빼주는 방식도 처리한다.
• 2-3. 최종적으로 확산이 이루어진 이후 보드판에 확산이 이루어진 배열을 더해준다.
• 3-1. air_upside함수를 만들어 공기청정기의 윗부분 (반시계방향)으로 먼지 이동 처리
• 3-2. air_downside함수 만들어 공기청정기의 아랫부분 (시계방향)으로 먼지 이동 처리
  -> 최종적으로 t만큼 해당 확산, 공기청정기 윗부분, 아랫부분 함수를 처리해주고 보드판의 남은 배열의 값들을 모두 합산하여 출력