[Samsung] 2021-2 오전 2번 냉각시스템
[Samsung] 2021-2 오전 2번 냉각시스템
Question
Language: Python
Difficulty: Platinum 5
해당 문제에서 구현해야될 부분은 크게 3가지이다.
- 초기화
- 에어컨의 작동
- 시원함의 전파
- 외벽 부분의 시원함 감소
각 세부 과정은 아래와 같다
- 초기화
해당 문제에서 사용되는 변수들을 초기화하는 과정이다.
fresh_map은 각 좌표의 시원함을, wall_map은 각 좌표에 대해 4방향에 대하여 벽이 있는 지 여부를 저장하는 배열이다. wall_map과 같이 4방향을 모두 저장하고 있어 각 좌표에 대해 방향 이동 과정에서 벽의 유무를 간단하게 확인하는 것이 가능하다.
offices은 사무실의 좌표정보, air_conditioners은 에어컨의 좌표, 방향을 저장하고 있다.
fresh_map=[[0] * n for _ in range(n)]
wall_map=[[[False]*4 for _ in range(n)] for _ in range(n)]
offices=[]
air_conditioners=[]
for row in range(n):
for col in range(n):
#빈칸인 경우
if board[row][col]==0:
continue
#사무실
if board[row][col]==1:
offices.append((row,col))
#에어컨
else:
air_conditioners.append((row,col,board[row][col]-2))
#벽의 좌표 표시
for row,col,wall_dir in walls:
row-=1
col-=1
#윗쪽으로 나있으면
if wall_dir==0:
wall_map[row][col][1]=True
#위의 좌표의 아랫쪽에 벽이있음을 표시
if row -1 >=0:
wall_map[row-1][col][3]=True
#왼쪽으로 나있으면
else:
wall_map[row][col][0]=True
#왼쪽 좌표의 오른쪽에 벽이있음을 표시
if col-1>=0:
wall_map[row][col-1][2]=True
- 에어컨 동작
에어컨 동작 과정은 아래의 그림과 같이 동작한다.
해당 그림은 에어컨이 동쪽으로 향해있을때의 시원함이 전파하는 과정을 다뤘지만, 어떠한 방향이 오더라도 위의 과정을 적용하는 것이 가능하다. 그래서 각 방향대로, 퍼질 수 있는 좌표를 확인하여 에어컨의 바람을 전파한다.
#에어컨 작동
def run_airconditioner(fresh_map,wall_map,air_conditioners):
for start_row,start_col,air_dir in air_conditioners:
next_row=start_row+dy[air_dir]
next_col=start_col+dx[air_dir]
#처음 전파되는 좌표
fresh_map[next_row][next_col]+=5
queue=deque([(next_row,next_col,4)])
visited=[[False]*n for _ in range(n)]
#오른쪽 방향을 기준으로 주석 달았음
while queue:
row,col,power=queue.popleft()
#파워가 0이면 더 이상 전파되지 않는다.
if power==0:
continue
#대각선 왼쪽 처리
#윗쪽 방향
up_air_dir=(air_dir-1)%4
#위 좌표
up_row=row+dy[up_air_dir]
up_col=col+dx[up_air_dir]
#오른쪽 위의 좌표
up_right_row=up_row+dy[air_dir]
up_right_col=up_col+dx[air_dir]
#왼쪽 대각선 위의 좌표가 격자를 벗어나지 않는지 확인
if check_range(up_row,up_col) and check_range(up_right_row,up_right_col):
#가는 방향에 벽이 있는 확인
if not wall_map[row][col][up_air_dir] and not wall_map[up_row][up_col][air_dir]:
#해당 자리를 이전에 처리했는지 확인
if not visited[up_right_row][up_right_col]:
fresh_map[up_right_row][up_right_col]+=power
visited[up_right_row][up_right_col]=True
queue.append((up_right_row,up_right_col,power-1))
#정방향
right_row=row+dy[air_dir]
right_col=col+dx[air_dir]
#왼쪽 대각선 위의 좌표가 격자를 벗어나지 않는지 확인
if check_range(right_row,right_col):
#가는 방향에 벽이 있는 확인
if not wall_map[row][col][air_dir]:
#해당 자리를 이전에 처리했는지 확인
if not visited[right_row][right_col]:
fresh_map[right_row][right_col]+=power
visited[right_row][right_col]=True
queue.append((right_row,right_col,power-1))
#대각선 오른쪽 처리
down_air_dir=(air_dir+1)%4
#아래 좌표
down_row=row+dy[down_air_dir]
down_col=col+dx[down_air_dir]
#오른쪽 아래의 좌표
down_right_row=down_row+dy[air_dir]
down_right_col=down_col+dx[air_dir]
#오른쪽 대각선 아래의 좌표가 격자를 벗어나지 않는지 확인
if check_range(down_row,down_col) and check_range(down_right_row,down_right_col):
#가는 방향에 벽이 있는 확인
if not wall_map[row][col][down_air_dir] and not wall_map[down_row][down_col][air_dir]:
#해당 자리를 이전에 처리했는지 확인
if not visited[down_right_row][down_right_col]:
fresh_map[down_right_row][down_right_col]+=power
visited[down_right_row][down_right_col]=True
queue.append((down_right_row,down_right_col,power-1))
- 시원함의 전파
각 좌표를 기준으로 인접한 칸에 대하여 시원함을 전파시킨다. 이때 시원함은 높은 곳에서 낮은 곳으로만 흐르고, 차이가 4보다 작게 되면 시원함이 전파되지 않는다는 점을 이용한다.
def spread_fresh_air(fresh_map,wall_map):
new_fresh_map=[[0] *n for _ in range(n)]
for row in range(n):
for col in range(n):
value=fresh_map[row][col]
total_spread_value=0
for dir in range(4):
next_row=row+dy[dir]
next_col=col+dx[dir]
#범위를 벗어나는 경우
if not check_range(next_row,next_col):
continue
#해당 진행방향에 벽이 있는 경우 퍼지지 않는다.
if wall_map[row][col][dir]:
continue
#현재 좌표의 시원함이 인접한 좌표의 시원함보다 4 차이 이상 나지 않는 경우 퍼지지 않는다.
if value-fresh_map[next_row][next_col] < 4:
continue
spread_value=(value-fresh_map[next_row][next_col])//4
new_fresh_map[next_row][next_col]+=(spread_value)
total_spread_value+=spread_value
#다 퍼지고 남은 만큼은 원래 좌표에 넣는다.
new_fresh_map[row][col]+=(value-total_spread_value)
#시원함이 퍼진이후의 갱신
for row in range(n):
for col in range(n):
fresh_map[row][col]=new_fresh_map[row][col]
- 외벽에 인접한 좌표에 대한 시원함 감소
#외벽에 맞다있는 좌표에 대해 시원함 감소
def lose_fresh(fresh_map):
#가로줄
for col in range(n):
if fresh_map[0][col] > 0:
fresh_map[0][col]-=1
if fresh_map[n-1][col] > 0:
fresh_map[n-1][col]-=1
#세로줄
for row in range(1,n-1):
if fresh_map[row][0]> 0:
fresh_map[row][0]-=1
if fresh_map[row][n-1]>0:
fresh_map[row][n-1]-=1
Solution
from collections import deque
def check_range(row,col):
if row < 0 or row >=n or col < 0 or col >=n:
return False
return True
#사무실 온도 확인
def check_office_temperature(fresh_map,offices):
for row,col in offices:
if fresh_map[row][col] < k:
return False
return True
#에어컨 작동
def run_airconditioner(fresh_map,wall_map,air_conditioners):
for start_row,start_col,air_dir in air_conditioners:
next_row=start_row+dy[air_dir]
next_col=start_col+dx[air_dir]
#처음 전파되는 좌표
fresh_map[next_row][next_col]+=5
queue=deque([(next_row,next_col,4)])
visited=[[False]*n for _ in range(n)]
#오른쪽 방향을 기준으로 주석 달았음
while queue:
row,col,power=queue.popleft()
#파워가 0이면 더 이상 전파되지 않는다.
if power==0:
continue
#대각선 왼쪽 처리
#윗쪽 방향
up_air_dir=(air_dir-1)%4
#위 좌표
up_row=row+dy[up_air_dir]
up_col=col+dx[up_air_dir]
#오른쪽 위의 좌표
up_right_row=up_row+dy[air_dir]
up_right_col=up_col+dx[air_dir]
#왼쪽 대각선 위의 좌표가 격자를 벗어나지 않는지 확인
if check_range(up_row,up_col) and check_range(up_right_row,up_right_col):
#가는 방향에 벽이 있는 확인
if not wall_map[row][col][up_air_dir] and not wall_map[up_row][up_col][air_dir]:
#해당 자리를 이전에 처리했는지 확인
if not visited[up_right_row][up_right_col]:
fresh_map[up_right_row][up_right_col]+=power
visited[up_right_row][up_right_col]=True
queue.append((up_right_row,up_right_col,power-1))
#정방향
right_row=row+dy[air_dir]
right_col=col+dx[air_dir]
#왼쪽 대각선 위의 좌표가 격자를 벗어나지 않는지 확인
if check_range(right_row,right_col):
#가는 방향에 벽이 있는 확인
if not wall_map[row][col][air_dir]:
#해당 자리를 이전에 처리했는지 확인
if not visited[right_row][right_col]:
fresh_map[right_row][right_col]+=power
visited[right_row][right_col]=True
queue.append((right_row,right_col,power-1))
#대각선 오른쪽 처리
down_air_dir=(air_dir+1)%4
#아래 좌표
down_row=row+dy[down_air_dir]
down_col=col+dx[down_air_dir]
#오른쪽 아래의 좌표
down_right_row=down_row+dy[air_dir]
down_right_col=down_col+dx[air_dir]
#오른쪽 대각선 아래의 좌표가 격자를 벗어나지 않는지 확인
if check_range(down_row,down_col) and check_range(down_right_row,down_right_col):
#가는 방향에 벽이 있는 확인
if not wall_map[row][col][down_air_dir] and not wall_map[down_row][down_col][air_dir]:
#해당 자리를 이전에 처리했는지 확인
if not visited[down_right_row][down_right_col]:
fresh_map[down_right_row][down_right_col]+=power
visited[down_right_row][down_right_col]=True
queue.append((down_right_row,down_right_col,power-1))
#시원함 퍼짐
def spread_fresh_air(fresh_map,wall_map):
new_fresh_map=[[0] *n for _ in range(n)]
for row in range(n):
for col in range(n):
value=fresh_map[row][col]
total_spread_value=0
for dir in range(4):
next_row=row+dy[dir]
next_col=col+dx[dir]
#범위를 벗어나는 경우
if not check_range(next_row,next_col):
continue
#해당 진행방향에 벽이 있는 경우 퍼지지 않는다.
if wall_map[row][col][dir]:
continue
#현재 좌표의 시원함이 인접한 좌표의 시원함보다 4 차이 이상 나지 않는 경우 퍼지지 않는다.
if value-fresh_map[next_row][next_col] < 4:
continue
spread_value=(value-fresh_map[next_row][next_col])//4
new_fresh_map[next_row][next_col]+=(spread_value)
total_spread_value+=spread_value
#다 퍼지고 남은 만큼은 원래 좌표에 넣는다.
new_fresh_map[row][col]+=(value-total_spread_value)
#시원함이 퍼진이후의 갱신
for row in range(n):
for col in range(n):
fresh_map[row][col]=new_fresh_map[row][col]
#외벽에 맞다있는 좌표에 대해 시원함 감소
def lose_fresh(fresh_map):
#가로줄
for col in range(n):
if fresh_map[0][col] > 0:
fresh_map[0][col]-=1
if fresh_map[n-1][col] > 0:
fresh_map[n-1][col]-=1
#세로줄
for row in range(1,n-1):
if fresh_map[row][0]> 0:
fresh_map[row][0]-=1
if fresh_map[row][n-1]>0:
fresh_map[row][n-1]-=1
def solution():
fresh_map=[[0] * n for _ in range(n)]
wall_map=[[[False]*4 for _ in range(n)] for _ in range(n)]
offices=[]
air_conditioners=[]
for row in range(n):
for col in range(n):
#빈칸인 경우
if board[row][col]==0:
continue
#사무실
if board[row][col]==1:
offices.append((row,col))
#에어컨
else:
air_conditioners.append((row,col,board[row][col]-2))
#벽의 좌표 표시
for row,col,wall_dir in walls:
row-=1
col-=1
#윗쪽으로 나있으면
if wall_dir==0:
wall_map[row][col][1]=True
#위의 좌표의 아랫쪽에 벽이있음을 표시
if row -1 >=0:
wall_map[row-1][col][3]=True
#왼쪽으로 나있으면
else:
wall_map[row][col][0]=True
#왼쪽 좌표의 오른쪽에 벽이있음을 표시
if col-1>=0:
wall_map[row][col-1][2]=True
time=0
while True:
if check_office_temperature(fresh_map,offices) or time>100:
break
run_airconditioner(fresh_map,wall_map,air_conditioners)
spread_fresh_air(fresh_map,wall_map)
lose_fresh(fresh_map)
time+=1
print(time if time <=100 else -1)
if __name__ == "__main__":
n,m,k=map(int,input().split())
board=[list(map(int,input().split())) for _ in range(n)]
walls=[list(map(int,input().split())) for _ in range(m)]
dy=[0,-1,0,1]
dx=[-1,0,1,0]
solution()
댓글남기기