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

https://www.codetree.ai/training-field/frequent-problems/problems/cooling-system/description?page=1&pageSize=20 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제종류

dx dy techinque, simulation

풀이시간

설계: 30분, 구현: 80분

풀이방법

에어컨에서 바람이 부는 로직을 설계하기 위해 적절한 자료구조를 활용하는 것이 중요하다. 

특정 격자에 벽이 존재하는 경우 바람이 더이상 전파 될 수 없는 조건을 만족하는 코드를 작성하기 위한 배열을 아래와 같이 선언하고

벽정보: wall[x][y][d]

바람이 불때 진행하려는 방향이 격자 밖을 벗어나거나 진행하려는 방향에 벽이 존재할 경우를 아래 로직을 통해 판별했다.

not wall[x][y][d] and 0 <= x < n and 0 <= y < n and wall[nx][ny][d^2]

코드

from copy import deepcopy

# 설계 20분
# 왼 위 오 아
dx, dy = [0, -1, 0, 1], [-1, 0, 1, 0]
# 다음 방향 정보, 정렬 기준
spread_info = {
    0: ([[1, 0], [3, 0]], 0),
    1: ([[0, 1], [2, 1]], 1),
    2: ([[1, 2], [3, 2]], 0),
    3: ([[0, 3], [2, 3]], 1)
}


def can_go_diag(sx, sy, n, path, wall):
    for d in path:
        nx, ny = sx + dx[d], sy + dy[d]
        if in_range(nx, ny, d, n, wall):
            sx, sy = nx, ny
            continue
        return -1, -1
    return sx, sy


def in_range(x, y, d, n, wall):
    bx, by = x + dx[d ^ 2], y + dy[d ^ 2]
    # 가려는곳이 범위안이거나 에어컨이 없을 경우
    return not wall[bx][by][d] and 0 <= x < n and 0 <= y < n and not wall[x][y][d ^ 2]


def chk_all(arr, wind, k):
    for i in range(len(arr)):
        for j in range(len(arr)):
            if arr[i][j] == 1 and wind[i][j] < k:
                return False
    return True


def main():
    N, M, K = map(int, input().split())
    arr = [list(map(int, input().split())) for i in range(N)]
    wind = [[0] * N for i in range(N)]
    # 에어컨 벽 정보
    wall = [[[0] * 4 for i in range(N)] for i in range(N)]
    parr = []
    # 에어컨 정보 (x,y,d)
    air = []
    ans = -1

    for i in range(N):
        for j in range(N):
            # 사무실 공간
            if arr[i][j] == 1:
                parr.append((i, j))
            if arr[i][j] >= 2:
                air.append((i, j, arr[i][j] - 2))

    for _ in range(M):
        x, y, d = map(int, input().split())
        x -= 1
        y -= 1
        d ^= 1
        wall[x][y][d] = 1
    for turn in range(100):
        # 에어컨 바람 불기
        for ax, ay, ad in air:
            # 5부터 1까지
            # 좌표 저장
            path_arr, sort_key = spread_info[ad]
            zp, lp = path_arr
            if not in_range(ax + dx[ad], ay + dy[ad], ad, N, wall):
                continue
            ax += dx[ad]
            ay += dy[ad]
            wind[ax][ay] += 5
            flow_arr = set()
            flow_arr.add((ax, ay))
            for w in range(4, 0, -1):
                # 전파할 곳 없으면 break
                if len(flow_arr) == 0:
                    break
                # 끝 정보 구하기
                next_flow_arr = set()

                # 자기 자신의 방향으로 전파
                for tx, ty in flow_arr:
                    nx, ny = tx + dx[ad], ty + dy[ad]
                    if in_range(nx, ny, ad, N, wall):
                        next_flow_arr.add((nx, ny))

                for tx, ty in flow_arr:
                    nsx, nsy = can_go_diag(tx, ty, N, zp, wall)
                    nex, ney = can_go_diag(tx, ty, N, lp, wall)
                    for nxx, nyy in [(nsx, nsy), (nex, ney)]:
                        if (nxx, nyy) != (-1, -1):
                            next_flow_arr.add((nxx, nyy))

                # 값 더해주기
                for tx, ty in next_flow_arr:
                    wind[tx][ty] += w
                flow_arr = {*next_flow_arr}
        # 에어컨 바람 섞이기
        air_diff = []
        for r in range(N):
            for c in range(N):
                cur = wind[r][c]
                tdiff = 0
                for k in range(4):
                    nx, ny = r + dx[k], c + dy[k]
                    if in_range(nx, ny, k, N, wall) and wind[nx][ny] < cur:
                        diff = (cur - wind[nx][ny]) // 4
                        air_diff.append((nx, ny, diff))
                        tdiff += diff
                air_diff.append((r, c, -tdiff))
        for r, c, diff in air_diff:
            wind[r][c] += diff
        # 외벽 감소

        # 오 아 왼 위
        bx, by = [0, 1, 0, -1], [1, 0, -1, 0]
        cx, cy = 0, 0
        for bd in range(4):
            for j in range(N - 1):
                wind[cx][cy] = max(wind[cx][cy] - 1, 0)
                cx, cy = cx + bx[bd], cy + by[bd]

        # 사무실공간이 다 채워졌으면
        if chk_all(arr, wind, K):
            ans = turn + 1
            break
    # 외벽에 있는 시원한 칸 1 감소하기
    print(ans)


main()