Easy is Perfect

[백준] 20058번 마법사 상어와 파이어스톰 _ 문제 풀이

  • melonicedlatte
  • Mar 27, 2021


1. 문제

https://www.acmicpc.net/problem/20058

2. 풀이

삼성 SW 역량테스트 문제입니다. 풀이는 주석을 통하여 전개했으니, 소스코드를 확인해주세요. 추가로 아래와 같은 시행착오를 겪었습니다.

  • 처음에 문제를 잘 못 이해하여, 풀이에 시간이 오래 걸렸습니다. 백준 문제 질문 을 통해서 확인해보니 아래의 답변을 통해 해결할 수 있었습니다. 예제에서 나온 그림을 보면 아래처럼 이해해도 해결이 되어 이런 문제가 발생했습니다. 답변 주신 분 감사합니다.

    skh2080 : 레벨 2면 4x4 행렬 안에서 2x2 4개가 시계방향으로 돈다고 생각하셨죠? 그게 아니라 4x4행렬의 row 1이 새로운 4x4 행렬의 col 4, row 2가 col 3, row 3가 col 2, row 4가 col 1… 이런식으로 행 단위로 바뀐단 거에요

  • Test 중에 python3는 시간 초과가 발생합니다.
  • pypy3를 사용하면 sys.setrecursionlimit 함수를 사용하여야 합니다. 그렇지 않은 경우에는 RecursionError가 발생합니다. 해당 함수에 인자는 10 * 4, 10 * 5 는 가능했지만 10 * 6 의 경우 메모리 초과가 발생하였습니다. 다른 분의 경우 10 * 6으로 해결했다고 하여 사용해보았지만, 저 같은 경우에는 문제가 발생했습니다.
import sys
sys.setrecursionlimit(10**4)

N, Q = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(2**N)]
magic_list = list(map(int, input().split()))
# 상우하좌
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
is_visted = [[False] * (2 ** N) for _ in range(2 ** N)]


# 주어진 크기만큼 map을 시계 방향으로 돌림
def rotate(L):
    global maps
    if L == 0:
        return
    copy_map = [[maps[x][y] for y in range(2 ** N)] for x in range(2 ** N)]
    # 시작점 모서리
    rec_size = 2**L
    for r in range(0, 2**N, rec_size):
        for c in range(0, 2 ** N, rec_size):
            # 왼쪽 상단 copy
            for x in range(rec_size):
                for y in range(rec_size):
                    maps[r+y][c+rec_size-1-x] = copy_map[r+x][c+y]


# 얼음을 확인하고 값을 깎음
def ice_melt():
    melt_list = []
    # 인접한 칸 확인
    for r in range(2**N):
        for c in range(2**N):
            side_ice_num = 0
            for side_idx in range(4):
                side_row = r + dr[side_idx]
                side_col = c + dc[side_idx]
                if side_row < 0 or side_row >= 2**N or side_col < 0 or side_col >= 2**N:
                    continue
                if maps[side_row][side_col] > 0:
                    side_ice_num += 1

            if side_ice_num < 3:
                melt_list.append((r, c))

    for one_melt in melt_list:
        r, c = one_melt[0], one_melt[1]
        maps[r][c] = maps[r][c]-1 if maps[r][c] else 0


def get_big_dungery(r,c):
    global is_visted
    if r < 0 or r >= 2 ** N or c < 0 or c >= 2 ** N or is_visted[r][c] or maps[r][c] == 0:
        return 0
    is_visted[r][c] = True
    sub_dungery = 1
    for side_idx in range(4):
        sub_dungery += get_big_dungery(r + dr[side_idx], c + dc[side_idx])
    return sub_dungery


for magic in magic_list:
    rotate(magic)
    ice_melt()
# 남은 얼음의 합
print( sum([sum(x) for x in maps]) )
# 가장 큰 덩어리가 차지하는 개수

big_dungery = 0
for r in range(2 ** N):
    for c in range(2 ** N):
        big_dungery = max(get_big_dungery(r,c), big_dungery)
print( big_dungery )



Search