백준 17144 : 미세먼지 안녕!

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

17144번: 미세먼지 안녕!

 미세먼지 확산하는 것은 어렵지 않았으나, 공기청정기 작동방식 구현하는 것이 조금 까다로웠던 문제.

 

 1. 미세먼지 확산

 미세먼지 확산은 동시에 확산한다고 하나, 프로그래밍은 순차적으로 진행하기 때문에 Board를 그대로 이용하는 순간 난장판이 되어버린다. 참조되기전에 확산한 먼지가 참조될때 자리 잡고 있으면 같이 계산 때려버림. 그러므로 먼지의 정보를 따로 저장해두고 계산해야한다. 매 시간마다 먼지의 위치정보를 초기화 시켜서 확산하도록 했다.

dust = []
for i in range(R) :
    for j in range(C) :
        if board[i][j] > 0 :
            dust.append([i, j, board[i][j]])
if time == T :
    break
for i, j, d in dust :
    A = d // 5
    cnt = 0
    for k in range(4) :
        nx = i + dx[k]
        ny = j + dy[k]
        if nx < 0 or nx >= R or ny < 0 or ny >= C :
            continue
        if board[nx][ny] == -1 :
            continue
        board[nx][ny] += A
        cnt += 1
    board[i][j] -= A * cnt

 2. 공기 청정기 작동

  공기청정기는 윗부분과 아랫부분이 서로 반대 방향으로 작동한다. 공기청정기의 좌표정보와 위/아래 정보를 활용하여 먼지들이 이동하므로 먼지들의 좌표만 바꿔주면 된다. 

 공기청정기의 작동 방향이 다음과 같을 때 공기청정기 윗부분에 대해 1차원으로 펼치면 다음과 같이 된다.

 1차원 리스트라고 했을 때, 0번 인덱스에 0을 추가해주고, 맨 마지막 인덱스를 제거해주면 회전완료.

공기청정기 아래쪽도 동일하게 진행해주면 된다. 어떻게 리스트를 구성할 것인가 동일하게 인덱싱이 가능하도록 잘 고려하면 쉽게 구현할 수 있다.

# 공기 청정기 작동
for x, y, k in air :
    d = 0
    dust_list = []
    ax, ay = x, y
    while True :
        nx = ax + dx[d]
        ny = ay + dy[d]
        # 공기청정기 바람 이동 벽에 부딫히면 반시계 방향 이동
        if nx < 0 or nx >= R or ny < 0 or ny >= C :
            d = direction(d, k)
            continue
        ax, ay = nx, ny
        if nx == x and ny == y : break
        dust_list.append(board[nx][ny])
    del dust_list[-1]
    dust_list.insert(0, 0)

 3. 전체 코드

메모리 146416 KB 시간 576 ms 문제 풀이시간 : 87 m 46 s

앞으로 풀이시간도 적어놔야겠다. 아주 조금씩 풀이속도가 빨라지고 있다.

R, C, T = map(int, input().split())
board = []
air = []
it = 0 # 위는 0 아래는 1
for i in range(R) :
    info = list(map(int, input().split()))
    board.append(info)
    for j in range(len(info)) :
        if info[j] == -1 :
            air.append([i, j, it])
            it += 1
# 우, 상, 좌, 하
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]

def direction(d, key) :
    if key == 0 : # 위
        d += 1
    else : # 아래
        d -= 1
    return d

def solve() :
    time = 0
    while True :
        # 미세먼지 확산
        dust = []
        for i in range(R) :
            for j in range(C) :
                if board[i][j] > 0 :
                    dust.append([i, j, board[i][j]])
        if time == T :
            break
        for i, j, d in dust :
            A = d // 5
            cnt = 0
            for k in range(4) :
                nx = i + dx[k]
                ny = j + dy[k]
                if nx < 0 or nx >= R or ny < 0 or ny >= C :
                    continue
                if board[nx][ny] == -1 :
                    continue
                board[nx][ny] += A
                cnt += 1
            board[i][j] -= A * cnt
        # 공기 청정기 작동
        for x, y, k in air :
            d = 0
            dust_list = []
            ax, ay = x, y
            while True :
                nx = ax + dx[d]
                ny = ay + dy[d]
                # 공기청정기 바람 이동 벽에 부딫히면 반시계 방향 이동
                if nx < 0 or nx >= R or ny < 0 or ny >= C :
                    d = direction(d, k)
                    continue
                ax, ay = nx, ny
                if nx == x and ny == y : break
                dust_list.append(board[nx][ny])
            del dust_list[-1]
            dust_list.insert(0, 0)
            ax, ay = x, y
            it, d = 0, 0
            while True : # Board 업데이트
                nx = ax + dx[d]
                ny = ay + dy[d]
                if nx < 0 or nx >= R or ny < 0 or ny >= C :
                    d= direction(d, k)
                    continue
                ax, ay = nx, ny
                if nx == x and ny == y : break
                board[nx][ny] = dust_list[it]
                it += 1
        time += 1
    result = 0
    for i, j, k in dust :
        result += k
    return result

print(solve())