[CodeTree] 냉방 시스템 - 삼성 SW 역량테스트 2021 하반기 오전 2번 문제

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

 

문제 분석

• N*N으로 이뤄진 격자에 0 ~ 5까지 값이 저장되어 있음. (0부터 5까지 차례대로 빈 공간 / 사무실 / 왼쪽 방향 에어컨 / 위쪽 방향 에어컨 / 오른쪽 방향 에어컨 / 아래쪽 방향 에어컨)
• 에어컨은 아래 그림처럼 시작점 기준으로 시계 45', 반시계 45', 그리고 직선 방향으로 확산 과정을 수행함.
• 시계 / 반시계 방향으로 시원함 확산을 수행할 때는, 바로 대각선으로 전파되는 것이 아닌 위(아래) 이동 후 기존 확산 방향으로 이동하는 두 단계를 거쳐 작업을 수행함.
• 새로운 시원함의 생성은, 모든 에어컨으로부터 나오는 시원함의 합으로 이뤄지며, 기존에 에어컨이 위치하던 자리 또한 시원함이 생길 수 있음.

에어컨 바람 확산 예시

• 모든 에어컨의 시원함이 확산된 후, 시원한 공기들은 서로 섞이기 시작함.
• 4방향 중 이동할 수 있는 (벽이 없는) 인접한 칸에 한하여 시원함이 높은 곳에서 낮은 곳으로 ⌊시원함의 차이 / 4⌋만큼 전파되며, 이 과정은 모든 칸이 동시에 이뤄짐.
• 전파 이후, 외벽과 맞닿아있는 칸의 경우 시원함이 1씩 감소함.
• 위 과정을 모두 수행하면 1분이라는 시간이 흐르게 되고, 모든 사무실 내 시원함이 K 이상이 되는 최소한의 시간을 Return하는 문제.

 

문제 접근

• 초기 자료구조 정의
  • 사무실의 좌표와 벽의 여부를 판단할 때 발생하는 시간 복잡도를 O(1)로 만들고자 set() 자료구조로 정의.
  • 입력받는 N*N 격자 내 에어컨의 값이 2부터 (좌, 상, 우, 하) 순서로 정의되기 때문에, 이에 맞게 이동 방향을 저장한 direc 배열 선언.
  • 1차례 에어컨의 확산 정보를 저장하는 new_field 배열과, 누적 시원함을 저장할 score 배열 선언.
• 에어컨 확산을 저장하는 경우
  • 각 에어컨의 (x, y, d) 정보를 활용하여 시원함 확산 과정을 수행함.
  • 에어컨이 있는 위치에서 에어컨이 바라보는 방향으로 한 칸을 이동한 지점이 확산 시작 지점이며, bfs를 위한 queue의 초기 값으로 활용.
  • 우측을 바라보는 경우에 대각선 확산 과정은 결국엔 위(아래) 이동 후 오른쪽 이동이며, 위/아래로 이동 가능한지 여부를 먼저 판단. 그 후, 가능하다면 search_pts에 push하여 한 번에 이동 관리.
  • 동일한 위치를 여러번 반복하면 안되기 때문에, 방문 처리를 수행.
  • 모든 에어컨의 확산이 종료된 시점에, score 배열에 new_field 배열 값을 복사함. 그 이유는, 1턴이 종료된 후에는 굳이 에어컨 확산을 중복하여 수행할 필요가 없이, 값만 더해주면 되기 때문에 이 둘을 나눠서 관리함.
  • 2번째 에어컨 확산부터는 new_field의 값을 score에 더해주는 방식으로 중복 연산 제거.
• 인접한 칸으로 시원함 확산
  • 인접한 칸 중 범위를 넘어가거나, 현재 위치의 값보다 작은 경우, 혹은 벽으로 인해 이동하지 못하는 경우는 pass.
  • 그렇지 않은 모든 case에 대하여 차이를 구하고, 4로 나눈 몫만큼 값을 빼주는 작업을 수행.
  • 이 과정은 동시에 진행되기 때문에, 추가 연산을 수행할 values 배열을 생성함.
• 시원함 최종 업데이트 (턴 종료)
  • values에 있는 값을 score 배열에 더해주는 작업 수행.
  • 외벽에 존재하는 격자 칸의 시원함을 1빼주는 작업도 함께 수행.
• 종료 조건
  • 종료 조건은 모든 사무실의 시원함이 K이상인 경우에, 혹은 time이 100이 넘어가는 시점에 종료.
  • 초기 사무실의 좌표를 저장해두었던 rooms를 활용하여 각 사무실의 시원함을 체크하고, 종료 여부를 판단.

 

소스 코드

# define lib
import copy
from collections import deque, defaultdict

# set value from input
air_machine, rooms, walls = [], set(), set()
direc = [(0, -1), (-1, 0), (0, 1), (1, 0)]

n, m, k = map(int, input().split())
for i in range(n):
    line = list(map(int, input().split()))
    for j in range(n):
        if line[j] == 1:
            rooms.add((i, j))
        elif line[j] > 1:
            air_machine.append((i, j, line[j]-2))

for _ in range(m):
    sx, sy, sd = map(int, input().split())
    if sd == 0:
        nx, ny = sx+direc[1][0], sy+direc[1][1]
    else:
        nx, ny = sx+direc[0][0], sy+direc[0][1]
    walls.add((sx-1, sy-1, nx-1, ny-1))
    walls.add((nx-1, ny-1, sx-1, sy-1))

# run
time = 0
new_field = [[0]*n for _ in range(n)]
score = None
while time < 100:
    # remove duplicate cals
    if time >= 1:
        for i in range(n):
            for j in range(n):
                score[i][j] += new_field[i][j]
    else:    
    # wind
        for ax, ay, ad in air_machine:
            ax, ay = ax+direc[ad][0], ay+direc[ad][1]
            new_field[ax][ay] += 5
            dq, visit = deque([(ax, ay, 5)]), set()
            visit.add((ax, ay))
            while dq:
                cx, cy, cv = dq.popleft()
                if cv == 0:
                    continue
                search_pts = [(cx, cy)]

                # upper / lower arrow
                for nad in [(ad-1)%4, (ad+1)%4]:
                    nx, ny = cx+direc[nad][0], cy+direc[nad][1]
                    if (0 <= nx < n) and (0 <= ny < n) and (nx, ny) not in visit:
                        if (nx, ny, cx, cy) not in walls and (cx, cy, nx, ny) not in walls:
                            search_pts.append((nx, ny))

                # line
                for tx, ty in search_pts:
                    nx, ny = tx+direc[ad][0], ty+direc[ad][1]
                    if (0 <= nx < n) and (0 <= ny < n) and (nx, ny) not in visit:
                        if (nx, ny, tx, ty) not in walls and (tx, ty, nx, ny) not in walls:
                            visit.add((nx, ny))
                            new_field[nx][ny] += cv-1
                            dq.append((nx, ny, cv-1))
        score = copy.deepcopy(new_field)

    # spread
    values = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for nk in range(4):
                nx, ny = i+direc[nk][0], j+direc[nk][1]
                if nx < 0 or nx >= n or ny < 0 or ny >= n or score[i][j] < score[nx][ny]:
                    continue
                if (nx, ny, i, j) not in walls and (i, j, nx, ny) not in walls:
                    tmp = (score[i][j]-score[nx][ny])//4
                    values[i][j], values[nx][ny] = values[i][j]-tmp, values[nx][ny]+tmp

    # update
    for i in range(n):
        for j in range(n):
            score[i][j] += values[i][j]
            if i == 0 or i == n-1 or j == 0 or j == n-1:
                score[i][j] = max(score[i][j] - 1, 0)

    # check
    time += 1
    exit_flag = True
    for px, py in rooms:
        if score[px][py] < k:
            exit_flag = False
            break
    
    if exit_flag:
        break

print(-1 if time >= 100 else time)

• 제출 횟수: 3회
• 풀이 시간: 90분