[코드트리:냉방시스템]

url : https://www.codetree.ai/training-field/frequent-problems/problems/cooling-system/description?page=1&pageSize=20
푼시간 : 3시간
레벨 : 플레티넘 5

# 설계 11분
# 격자크기, 벽의 개수, 원하는 시원함 정도
N, M, K = map(int, input().split())
aircondition = [[] for _ in range(4)]
arr = [[0 for _ in range(N)] for _ in range(N)]

# 사무실
room = []
for i in range(N):
    list_ = list(map(int, input().split()))
    for j in range(N):
        if list_[j] == 1:
            room.append([i, j])
        if list_[j] >= 2:
            aircondition[list_[j] - 2].append([i, j])

# 상하좌우
wall = [[[0 for _ in range(4)] for _ in range(N)] for _ in range(N)]
for i in range(M):
    y, x, s = map(int, input().split())
    y -= 1
    x -= 1
    if s == 1:
        wall[y][x - 1][3] = 1
        wall[y][x][2] = 1
    else:
        wall[y - 1][x][1] = 1
        wall[y][x][0] = 1


def in_range(y, x):
    if 0 <= y < N and 0 <= x < N:
        return True
    return False


def left(arr, ay, ax):
    start = 5
    queue = []
    copy_arr = [[0 for _ in range(N)] for _ in range(N)]
    if wall[ay][ax + 1][2] == 0 and in_range(ay, ax + 1):
        copy_arr[ay][ax + 1] = start
        queue.append([ay, ax + 1, start])
    while len(queue) > 0:
        dy, dx, idx = queue.pop(0)
        if in_range(dy, dx + 1) and wall[dy][dx + 1][2] == 0:
            copy_arr[dy][dx + 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy, dx + 1, idx - 1])
        if in_range(dy - 1, dx) and in_range(dy - 1, dx + 1) and wall[dy - 1][dx][1] == 0 and wall[dy - 1][dx + 1][
            2] == 0:
            copy_arr[dy - 1][dx + 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy - 1, dx + 1, idx - 1])
        if in_range(dy + 1, dx) and in_range(dy + 1, dx + 1) and wall[dy + 1][dx + 1][2] == 0 and wall[dy + 1][dx][
            0] == 0:
            copy_arr[dy + 1][dx + 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy + 1, dx + 1, idx - 1])
    for i in range(N):
        for j in range(N):
            arr[i][j] += copy_arr[i][j]


# 오른쪽에서 쏨
def right(arr, ay, ax):
    start = 5
    queue = []
    copy_arr = [[0 for _ in range(N)] for _ in range(N)]
    if wall[ay][ax - 1][3] == 0 and in_range(ay, ax - 1):
        copy_arr[ay][ax - 1] = start
        queue.append([ay, ax - 1, start])
    while len(queue) > 0:
        dy, dx, idx = queue.pop(0)
        if in_range(dy, dx - 1) and wall[dy][dx - 1][3] == 0:
            copy_arr[dy][dx - 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy, dx - 1, idx - 1])
        if in_range(dy - 1, dx) and in_range(dy - 1, dx - 1) and wall[dy - 1][dx - 1][3] == 0 and wall[dy - 1][dx][
            1] == 0:
            copy_arr[dy - 1][dx - 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy - 1, dx - 1, idx - 1])
        if in_range(dy + 1, dx) and in_range(dy + 1, dx - 1) and wall[dy + 1][dx - 1][3] == 0 and wall[dy + 1][dx][
            0] == 0:
            copy_arr[dy + 1][dx - 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy + 1, dx - 1, idx - 1])
    for i in range(N):
        for j in range(N):
            arr[i][j] += copy_arr[i][j]


# 위에서 쏨
def up(arr, ay, ax):
    start = 5
    queue = []
    copy_arr = [[0 for _ in range(N)] for _ in range(N)]
    if wall[ay + 1][ax][0] == 0 and in_range(ay + 1, ax):
        copy_arr[ay + 1][ax] = start
        queue.append([ay + 1, ax, start])
    while len(queue) > 0:
        dy, dx, idx = queue.pop(0)
        if in_range(dy + 1, dx) and wall[dy + 1][dx][0] == 0:
            copy_arr[dy + 1][dx] = idx - 1
            if idx - 1 != 1:
                queue.append([dy + 1, dx, idx - 1])
        if in_range(dy, dx - 1) and in_range(dy + 1, dx - 1) and wall[dy][dx - 1][3] == 0 and wall[dy + 1][dx - 1][
            0] == 0:
            copy_arr[dy + 1][dx - 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy + 1, dx - 1, idx - 1])
        if in_range(dy, dx + 1) and in_range(dy + 1, dx + 1) and wall[dy][dx + 1][2] == 0 and wall[dy + 1][dx + 1][
            0] == 0:
            copy_arr[dy + 1][dx + 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy + 1, dx + 1, idx - 1])
    for i in range(N):
        for j in range(N):
            arr[i][j] += copy_arr[i][j]

# 아래에서 위로 쏨
def down(arr, ay, ax):
    start = 5
    queue = []
    copy_arr = [[0 for _ in range(N)] for _ in range(N)]
    if wall[ay - 1][ax][1] == 0 and in_range(ay - 1, ax):
        copy_arr[ay - 1][ax] = start
        queue.append([ay - 1, ax, start])
    while len(queue) > 0:
        dy, dx, idx = queue.pop(0)
        if in_range(dy - 1, dx) and wall[dy - 1][dx][1] == 0:
            copy_arr[dy - 1][dx] = idx - 1
            if idx - 1 != 1:
                queue.append([dy - 1, dx, idx - 1])
        if in_range(dy, dx - 1) and in_range(dy - 1, dx - 1) and wall[dy][dx - 1][3] == 0 and wall[dy - 1][dx - 1][
            1] == 0:
            copy_arr[dy - 1][dx - 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy - 1, dx - 1, idx - 1])
        if in_range(dy, dx + 1) and in_range(dy - 1, dx + 1) and wall[dy][dx + 1][2] == 0 and wall[dy - 1][dx + 1][
            1] == 0:
            copy_arr[dy - 1][dx + 1] = idx - 1
            if idx - 1 != 1:
                queue.append([dy - 1, dx + 1, idx - 1])
    for i in range(N):
        for j in range(N):
            arr[i][j] += copy_arr[i][j]


def mix(arr):
    X = [0, 0, -1, 1]
    Y = [-1, 1, 0, 0]
    diff = []
    for i in range(N):
        for j in range(N):
            for _ in range(4):
                dy = i + Y[_]
                dx = j + X[_]
                if not in_range(dy, dx) or arr[i][j] <= arr[dy][dx]: continue
                if wall[i][j][_] == 1: continue
                dif = (arr[i][j] - arr[dy][dx]) // 4
                if dif != 0:
                    diff.append([i, j, -dif])
                    diff.append([dy, dx, dif])
    for i, j, dif in diff:
        arr[i][j] += dif



def main():
    global arr
    time = 0
    while True:
        time += 1
        if time > 100:
            print(-1)
            break
        for i in range(4):
            if aircondition[i]:
                for ay, ax in aircondition[i]:
                    if i == 0:
                        right(arr, ay, ax)
                    elif i == 1:
                        down(arr, ay, ax)
                    elif i == 2:
                        left(arr, ay, ax)
                    else:
                        up(arr, ay, ax)
        # Mix
        mix(arr)
        #외벽 1 감소
        dy = 0
        dx = 1
        while dx < N - 1:
            arr[dy][dx] -= 1
            dx += 1
        while dy < N - 1:
            arr[dy][dx] -= 1
            dy += 1
        while dx > 0:
            arr[dy][dx] -= 1
            dx -= 1
        while dy >= 0:
            arr[dy][dx] -= 1
            dy -= 1

        for i in range(N):
            for j in range(N):
                arr[i][j] = max(0, arr[i][j])

        flag = 0
        for ry, rx in room:
            if arr[ry][rx] < K:
                flag = 1
                break

        if flag == 0:
            print(time)
            break
main()

문제설명

정보 :
0 -> 빈공간
1 -> 사무실 구역
2 -> 왼쪽 방향 향하는 에어컨
3 -> 위쪽 방향 향하는 에어컨
4 -> 오른쪽 방향 향하는 에어컨
5 -> 아래쪽 방향 향하는 에어컨

과정

1. 에어컨 바람 전파
   -
   - 이러한 형태로 총 세가지 방향으로 전파된다.
   - 전파되는 도중 벽이 존재하면 더이상 전파되지 않는다.
2. 섞임

• 인접한 칸들에 대해 높은곳 -> 낮은 곳으로 (시원함의 차이 // 4) 만큼 전파
  - 높은 곳은 -, 낮은 곳은 +
  • 벽을 사이에 둔 곳은 전파되지 않음

3. 외벽(끝에 있는 칸)에 있는 칸은 1씩 감소

구하는 것 -> 사무실 전체가 k이상 시원함이 되는 time을 구하라
단, 100분 넘을 경우 -1 출력하라

문제 풀이

1. 원래는 전파되는 게 모두 동일하고 방향만 달라지는 것이니까 그냥 회전을 시켜서 다 똑같이 오른쪽방향으로 바람이 나오는 걸로 생각하고 풀려고 했으나.. 회전이 너무너무 복잡해서 그냥 때려침
   그래서 실제로 상하좌우 방향에서 나오는 케이스를 일일이 함수로 분리해서 품 -> 그랬더니 중간중간 +, - 실수때문에 틀림! 하지만 다 고쳐서 맞긴함
2. 섞이는 경우는 한 칸당 4방향을 다 보면서 인접한 곳보다 높은 방향에서만 섞일 수 있도록 함.
   원래는 배열을 복사해서 하는 방식으로 풀었는데 명기님은 그 과정을 배열에 저장해서 다 나간뒤에 풀더라구 그래서 나도 똑같이 해봤는데 더 편함 -> 이 방식으로 풀기!
3. 외벽은 자꾸 두번씩 빼져서 문제였는데 디버깅으로 간단히 해결

후기

• 솔직히 플레 5정도까진 아닌 문제
• 근데 정말 이렇게 분리 다 하는게 맞는지는 의문 -> 이따가 비교해봐야지
• 테케 3번 틀려서 토론봤는데 에어컨 바로 앞을 벽으로 막는 경우 자체가 없는데 그걸로 질문하고 답변하고 있었음. 그 토론 이상하니 보지마시길