이 문제로 골4가 되었습니당 ~ ㅋ

문제 링크

17144 - 미세먼지 안녕!

문제 설명

r*c 크기의 집에 공기청정기를 설치하려고 한다. 공청기는 항상 1번 열에 설치되고, 세로로 두자리를 차지한다. $A_{r,c}$는 (r,c)칸의 미세먼지 양을 의미한다. 공청기 위치를 제외한 모든 칸에 부여된다.
1초간 다음과 같은 일이 일어난다.

1. 미세먼지의 확산
   : (r,c)의 인접한 4방향으로 $A_{r,c}$//5만큼의 미세먼지가 확산
   -> 벽이거나 공청기면 해당 칸으로는 확산 x
   -> $A_{r,c}$ = $A_{r,c}$ - ($A_{r,c}$//5)*(확산 칸의 수)
2. 공청기 작동

• 바람은 공청기의 윗칸 (x,1)은 반시계 방향으로 순환, 아래칸 (x+1,1)은 시계 방향으로 순환한다.
• 이 방향대로 먼지가 한칸씩 이동하고, 공청기로 들어간 미세먼지는 정화된다.
  
  T초 뒤에 방에 남은 미세먼지의 양을 구하세용

문제 풀이

문제 읽으면서 쉽네,, 했는데 처음에 설계를 잘못해서 디버깅하는데 꽤 걸렸다 ^_ㅠ

미세먼지가 확산되는 부분은 다음과 같이 구현했다.

# 해당 시간동안의 각 칸 확산량을 저장하는 리스트
check_room = [[0 for _ in range(C)] for _ in range(R)]
# 1. 미세먼지 확산
for i in range(R):
    for j in range(C):
        if room[i][j] > 0:
            # 미세먼지 있으면
            if room[i][j] >= 5:
                count = 0
                for d in range(4):
                    # 확산 가능한 네방향 체크
                    ni, nj = i+dx[d], j+dy[d]
                    if in_range(ni, nj) and room[ni][nj] != -1:
                        check_room[ni][nj] += room[i][j]//5
                        count += 1
                room[i][j] -= (room[i][j]//5)*count
for i in range(R):
    for j in range(C):
        room[i][j] += check_room[i][j]

1초동안 모든 칸에서 확산이 일어나는데 (0,0)부터 먼저 계산해서 더해줘버리면 이후의 결과에 영향을 미친다. 확산량을 새로운 리스트에 저장해서 다 확산된 후 결과를 더해줘야 한다.

공청기로 순환되는 부분은 다음과 같은 로직으로 구현하였다.

우선 dx, dy는 dx = [-1, 1, 0, 0], dy = [0, 0, -1, 1]으로 상-하-좌-우 순서이다. 두칸을 차지하는 공청기에서 윗칸을 공청기1, 아랫칸을 공청기2라고 했을때, 아래 그림에서 공청기1 기준으로 반시계방향으로 미는 부분을 생각해보자.

공청기1의 순환에서 공청기 방향으로 들어오는 맨 끝칸부터 차례대로 옮긴다. 기준 칸을 (x,y), 다음 칸을 x+dx[d],y+dy[d]인 (nx,ny)라고 했을때, room[x][y] <- room[nx][ny]로 먼지를 옮기고, x,y <- nx, ny로 갱신해 준다.

만약, nx, ny가 방의 범위를 벗어난 경우는 다음과 같이 경우를 나눠 nx,ny, 그리고 방향을 갱신했다.

공청기 2도 똑같이 경우를 나눠서 구현하면 된다.
코드는 다음과 같다.

# 2. 공청기 가동
for a in range(2):
    # 시계방향으로 확산시키기
    x, y, d = aircleaner[a][0]+dx[a], aircleaner[a][1], a
    while True:
        nx, ny = x+dx[d], y+dy[d]
        if (nx, ny) == aircleaner[a]:
            room[x][y] = 0
            break
        if a == 0:
            # 시계방향 확산일때
            if nx < 0:
                nx, ny = x, y+1
                d = 3
            elif nx > aircleaner[a][0]:
                nx, ny = x, y-1
                d = 2
            elif ny >= C:
                nx, ny = x+1, y
                d = 1
        elif a == 1:
            if nx >= R:
                nx, ny = x, y+1
                d = 3
            elif nx < aircleaner[a][0]:
                nx, ny = x, y-1
                d = 2
            elif ny >= C:
                nx, ny = x-1, y
                d = 0

        room[x][y] = room[nx][ny]
        x, y = nx, ny

전체 코드

import sys

input = sys.stdin.readline

# 상 하 좌 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def in_range(x, y):
    if x in range(R) and y in range(C):
        return True
    return False

R, C, T = map(int, input().split())
room = []
aircleaner = []
for i in range(R):
    tmp = list(map(int, input().split()))
    for j in range(C):
        if tmp[j] == -1:
            # 공청기 위치 기록
            aircleaner.append((i,j))
    room.append(tmp)

for time in range(T):
    check_room = [[0 for _ in range(C)] for _ in range(R)]
    # 1. 미세먼지 확산
    for i in range(R):
        for j in range(C):
            if room[i][j] > 0:
                # 미세먼지 있으면
                if room[i][j] >= 5:
                    count = 0
                    for d in range(4):
                        # 확산 가능한 네방향 체크
                        ni, nj = i+dx[d], j+dy[d]
                        if in_range(ni, nj) and room[ni][nj] != -1:
                            check_room[ni][nj] += room[i][j]//5
                            count += 1
                    room[i][j] -= (room[i][j]//5)*count
    for i in range(R):
        for j in range(C):
            room[i][j] += check_room[i][j]

    
    # 2. 공청기 가동
    for a in range(2):
        # 시계방향으로 확산시키기
        x, y, d = aircleaner[a][0]+dx[a], aircleaner[a][1], a
        while True:
            nx, ny = x+dx[d], y+dy[d]
            if (nx, ny) == aircleaner[a]:
                room[x][y] = 0
                break
            if a == 0:
                # 시계방향 확산일때
                if nx < 0:
                    nx, ny = x, y+1
                    d = 3
                elif nx > aircleaner[a][0]:
                    nx, ny = x, y-1
                    d = 2
                elif ny >= C:
                    nx, ny = x+1, y
                    d = 1
            elif a == 1:
                if nx >= R:
                    nx, ny = x, y+1
                    d = 3
                elif nx < aircleaner[a][0]:
                    nx, ny = x, y-1
                    d = 2
                elif ny >= C:
                    nx, ny = x-1, y
                    d = 0

            room[x][y] = room[nx][ny]
            x, y = nx, ny

answer = 0
for r in room:
    answer += sum(r)
print(answer + 2)

시키는 대로 하면 되는 이런 문제는 금방금방 풀어야 될 것 같은데 마음같지 않으네요 ,,,,, 코드로 옮기기 전에 수도코드를 얼마나 자세히 작성해야 효율적일지 아직 모르겠슴