[삼성/코테기출][Python][백준][20058] 마법사 상어와 파이어스톰 (시뮬레이션/구현)

🍋 문제링크

20058번: 마법사 상어와 파이어스톰

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 297264 KB

시간 : 1400 ms

🥝 메모

1. 깊은 복사와 얕은 복사

ice 의 배열을 tmp에 그대로 복사하기 위해서

tmp = ice

를 하면 얕은 복사를 하기 때문에 ice 배열의 원소를 변경하면 tmp 배열의 원소도 같이 변하기 때문에 tmp의 역할을 제대로 수행 할 수 없다. 따라서,

import copy tmp = **copy.deepcopy**(ice)

위와 같은 깊은 복사를 해주어야 한다.

2. 최대 재귀 깊이

Python이 정한 최대 재귀 깊이는 sys.getrecursionlimit()을 이용해 확인할 수 있다. BOJ의 채점 서버에서 이 값이 1,000으로 되어 있기 때문에 Python이 정한 최대 재귀 깊이보다 재귀의 깊이가 더 깊어질 때 **런타임에러(RecursionError)**가 발생하게 된다.

import sys sys.setrecursionlimit(10**5)

이를 방지하기 위해서는, 위의 코드와 같이 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)

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)

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)

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)

🍉 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)