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

문제

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

 

문제 풀이

 시뮬레이션 문제로, 문제에 주어진 조건을 그대로 구현하면 되는 문제이다. 문제에 제시된 조건은 다음과 같다.

1. `2 ^ L * 2 ^ L` 크기만큼의 격자를 시계 방향으로 90도 회전한다.
   • 90도로 회전하는 것은 L이 1인 경우는 다음과 같다.
   • `[[1, 2], [3, 4]]`가 있는 경우 `↑` 윗 방향으로 읽으면 `[3, 1], [4, 2]`가 된다.
   • 이를 `→` 우측으로 쓰게 되면 `[[3, 1], [4, 2]]`로 90도 회전한 결과를 얻을 수 있다.
2. 각 얼음에 인접한 얼음(상, 하, 좌, 우)의 개수가 3개 미만이라면 얼음이 녹아 1 감소한다.
   • (0, 0)과 같이 인접한 곳이 2인 곳이다.
   • 인접한 얼음이 0이라면, 얼음이 없는 것이다.
3. Q번 위의 1, 2 과정을 반복한다.
4. 남아 있는 얼음의 합과 남아 있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 출력한다.
   • 가장 큰 덩어리가 차지하는 칸의 개수는 얼음이 연결된 크기를 말한다.
   • 이는 백준: 2667 단지번호붙이기의 요구 사항과 동일하다.

 문제를 풀면서 주의할 사항은, 녹여야 하는 얼음을 즉시 처리하게 되면 문제가 발생한다. 다른 얼음의 탐색 과정에서 해당 얼음이 0이 되게 되면 지금 녹아야 할 얼음이 아닌데도 녹이는 상황이 발생하므로 주의하여야 한다.

 

 삼성 시뮬레이션 문제들은, 행렬을 조작하는 문제들이 많은 편이다. 따라서 비슷한 유형을 접하고 행렬을 조작하는 코드를 암기하는 것도 좋은 방법일 것 같다.

 

코드

from sys import stdin
from collections import deque


def visitable(r, c):
    return 0 <= r < N and 0 <= c < N and board[r][c]


def rotate(loc, l):
    cur_r, cur_c = loc

    '''
    예를 들어 격자에 값이 다음과 같다면,
    1 2             3 1
    3 4             4 2
    ↑로 읽고         →로 쓰면
    90도 회전
    '''
    for r in range(l):
        for c in range(l):
            # read ↑
            temp[r][c] = board[cur_r + l - 1 - c][cur_c + r]

    for r in range(l):
        for c in range(l):
            # write →
            board[cur_r + r][cur_c + c] = temp[r][c]


def simulation(l):
    # 1. 격자 크기 만큼 90도 회전.
    for r in range(0, N, l):
        for c in range(0, N, l):
            rotate((r, c), l)

    check = [[0 for _ in range(N)] for _ in range(N)]

    # 2-1. 인접한 얼음이 3개 미만인 경우 찾기.
    for r in range(N):
        for c in range(N):
            if not board[r][c]:
                continue

            adj_cnt = 0
            for dr, dc in dirs:
                next_r, next_c = r + dr, c + dc
                if visitable(next_r, next_c):
                    adj_cnt += 1

            # check 하지 않고, 바로 녹이게 되면 탐색에 영향을 받음.
            check[r][c] = 1 if adj_cnt < 3 else 0

    # 2-2. 찾은 얼음 녹이기.
    for r in range(N):
        for c in range(N):
            if check[r][c]:
                board[r][c] -= 1


# 백준: 4963 섬의 개수와 같은 로직
def bfs(start):
    q = deque([start])
    cnt = 1

    while q:
        cur_r, cur_c = q.popleft()
        for dr, dc in dirs:
            next_r, next_c = cur_r + dr, cur_c + dc

            if visitable(next_r, next_c) and not visited[next_r][next_c]:
                visited[next_r][next_c] = 1
                q.append((next_r, next_c))
                cnt += 1

    return cnt


if __name__ == '__main__':
    N, Q = map(int, stdin.readline().split())
    N = 2 ** N
    board = [list(map(int, stdin.readline().split())) for _ in range(N)]

    L = list(map(int, stdin.readline().split()))
    max_l = max(L)
    temp = [[0 for _ in range(2 ** max_l)] for _ in range(2 ** max_l)]
    visited = [[0 for _ in range(N)] for _ in range(N)]
    dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))

    for cur_l in L:
        simulation(2 ** cur_l)

    # Answer 1: 남아 있는 얼음의 총합.
    sum_ice = sum(sum(board, []))
    print(sum_ice)

    # Answer 2: 남아 있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수.
    max_ice = 0
    for i in range(N):
        for j in range(N):
            if board[i][j] and not visited[i][j]:
                visited[i][j] = 1
                max_ice = max(max_ice, bfs((i, j)))

    print(max_ice)

Python으로 제출하면 시간초과가 발생하는 코드이다.