문제링크
https://www.acmicpc.net/problem/20058
코드 제출 기록 (메모리 및 시간)
제출 날짜
@4/16/2021
메모리
297264 KB
시간
1400 ms
메모
•
2020 하반기 삼성전자 SW 역량 테스트
1. 깊은 복사와 얕은 복사
ice 의 배열을 tmp에 그대로 복사하기 위해서
tmp = ice
Python
복사
를 하면 얕은 복사를 하기 때문에 ice 배열의 원소를 변경하면 tmp 배열의 원소도 같이 변하기 때문에 tmp의 역할을 제대로 수행 할 수 없다. 따라서,
import copy
tmp = copy.deepcopy(ice)
Python
복사
위와 같은 깊은 복사를 해주어야 한다.
2. 최대 재귀 깊이
Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있다. BOJ의 채점 서버에서 이 값이 1,000으로 되어 있기 때문에 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때 런타임에러(RecursionError)가 발생하게 된다.
import sys
sys.setrecursionlimit(10**5)
Python
복사
이를 방지하기 위해서는, 위의 코드와 같이 sys.setrecursionlimit()을 사용하여 Python이 정한 최대 재귀 깊이를 변경하면 된다.
문제풀이
1. 2L × 2L 크기의 부분 격자 시계방향으로 90도 회전한다.
def rotate_ice(ice_width, box_width):
tmp = copy.deepcopy(ice)
for i in range(0, ice_width, box_width):
for j in range(0, ice_width, box_width):
for r in range(box_width):
for c in range(box_width):
ice[i+r][j+c] = tmp[i+box_width-1-c][j+r]
if __name__ == '__main__':
for L in L_list:
rotate_ice(ice_width, 2**L)
Python
복사
2. 얼음이 있는 칸 3개, 4개와 인접해있지 않은 칸은 얼음의 양이 1 줄어든다.
def melt_ice(dir, ice_width):
tmp = copy.deepcopy(ice)
for i in range(ice_width):
for j in range(ice_width):
cnt = 0
for d in dir:
if (0 <= i + d[0] < ice_width) and (0 <= j + d[1] < ice_width):
if tmp[i+d[0]][j+d[1]] > 0: cnt += 1
if cnt < 3 and ice[i][j] > 0:
ice[i][j] -= 1
if __name__ == '__main__':
for L in L_list:
melt_ice(dir, ice_width)
Python
복사
3. 1, 2 번 과정을 총 Q번 시전
4. 남아있는 얼음 A[r][c]의 합 계산
sum_all = 0
for i in range(ice_width):
sum_all += sum(ice[i])
print(sum_all)
Python
복사
5. 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수 계산
def dfs(ice, dir, x, y, ice_width):
ret = 1
for d in dir:
nx, ny = x + d[0], y + d[1]
if (0 <= nx < ice_width) and (0 <= ny < ice_width) and (ice[nx][ny] > 0):
ice[nx][ny] = 0
ret += dfs(ice, dir, nx, ny, ice_width)
return ret
if __name__ == '__main__':
ans = 0
for x in range(ice_width):
for y in range(ice_width):
if ice[x][y] > 0:
ice[x][y] = 0
ans = max(ans, dfs(ice, dir, x, y, ice_width))
print(ans)
Python
복사
Code
import copy
import sys
sys.setrecursionlimit(10**5)
ice = []
L_list = []
def rotate_ice(ice_width, box_width):
tmp = copy.deepcopy(ice)
for i in range(0, ice_width, box_width):
for j in range(0, ice_width, box_width):
for r in range(box_width):
for c in range(box_width):
ice[i+r][j+c] = tmp[i+box_width-1-c][j+r]
def melt_ice(dir, ice_width):
tmp = copy.deepcopy(ice)
for i in range(ice_width):
for j in range(ice_width):
cnt = 0
for d in dir:
if (0 <= i + d[0] < ice_width) and (0 <= j + d[1] < ice_width):
if tmp[i+d[0]][j+d[1]] > 0: cnt += 1
if cnt < 3 and ice[i][j] > 0:
ice[i][j] -= 1
def dfs(ice, dir, x, y, ice_width):
ret = 1
for d in dir:
nx, ny = x + d[0], y + d[1]
if (0 <= nx < ice_width) and (0 <= ny < ice_width) and (ice[nx][ny] > 0):
ice[nx][ny] = 0
ret += dfs(ice, dir, nx, ny, ice_width)
return ret
if __name__ == '__main__':
# 입력받기
N, Q = map(int, input().split())
ice_width = 2**N
for i in range(ice_width):
ice.append(list(map(int, input().split())))
L_list = list(map(int, input().split()))
dir = [[-1,0], [1,0],[0, -1], [0, 1]]
for L in L_list:
# 회전하기
rotate_ice(ice_width, 2**L)
# 0 인 것이 0, 1, 2 개면 -1
melt_ice(dir, ice_width)
# print(" ")
# for i in range(ice_width):
# print(ice[i])
# 전체 얼음의 합
sum_all = 0
for i in range(ice_width):
sum_all += sum(ice[i])
print(sum_all)
# 가장 큰 덩어리의 크기
ans = 0
for x in range(ice_width):
for y in range(ice_width):
if ice[x][y] > 0:
ice[x][y] = 0
ans = max(ans, dfs(ice, dir, x, y, ice_width))
print(ans)
Python
복사
