[BOJ20058 - Python] 마법사 상어와 파이어스톰

문제

---

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

 

2^N × 2^N 크기의 격자로 나누어진 얼음판이 주어진다.

 

파이어스톰 단계 L을 시전하면

1. 격자를 2^L × 2^L 크기의 부분 격자로 나눈다.

2. 모든 부분 격자를 시계 방향으로 90도 회전한다.

3. 얼음이 3개 미만으로 인접해있는 칸은 얼음의 양이 1씩 줄어든다.

 

 

파이어스톰을 총 Q번 시전하고 난 후,

(1) 남아있는 얼음의 합과 (2) 남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하는 것이 문제이다.

(덩어리 : 연결된 칸의 집합)

 

풀이

---

백준 알고리즘을 풀기 시작한지 얼마 안 된 potato로서.. 여태까지 접한 문제들 중 생각할 거리들, 배운 것들이 가장 많았던 문제였다,,,, 

 

고려해야 할 것들은 크게

1. 부분 격자 회전

2. 가장 큰 얼음 덩어리 찾기

이 두 가지였다.

 

차례차례 정리해 보자!

 

1. 부분 격자 회전

얼음의 양이 저장되어 있는 격자(ice)를 2^L × 2^L 크기의 부분 격자로 나눈 후, 부분 격자 하나하나를 시계 방향 90도 회전해야 한다.

 

먼저 부분 격자는 크기가 k인 정사각형, ice 배열 상에서의 시작 주소는 (y, x)라고 해보자.

 

부분 격자에 해당하는 정보들을 크기가 k인 임시 배열(temp)에 저장한 후, 시계 방향으로 90도 회전하였을 때의 값을 바로 ice에 덮어씌울 것이다.

 

temp에 값이 저장되어 있는 위치마다 ice 배열에 저장되어야 하는 위치를 한번 봐보자.

 

temp	ice
[0][0]	[y][x+k-1]
[0][1]	[y+1][x+k-1]
[0][2]	[y+2][x+k-1]
...	...
[1][0]	[y][x+k-1-1]
[1][1]	[y+1][x+k-1-1]
...	...
[2][0]	[y, x+k-1-2]
...	...
[i][j]	[y+j, x+k-1-i]

 

즉, temp[i][j]에 저장된 값은 시계 방향으로 90도 회전할 경우 ice[y+j][x+k-1-i]에 저장되어야 한다는 규칙을 찾을 수 있다.

* 번외 : 반시계 방향으로 90도 회전 시, temp[i][j]의 값은 ice[y+k-1-j][x+i]에 저장되어야 한다.

 

이 규칙을 통해 작성한 코드는 다음과 같다.

for L in level:
    k = 2 ** L

    # 부분 격자 시작 좌표 (y, x)
    for y in range(0, grid, k):  # grid = 2**N
        for x in range(0, grid, k):
        
            # 부분 격자 복사
            temp = [ice[i][x:x + k] for i in range(y, y + k)]

            # 회전
            for i in range(k):
                for j in range(k):
                    ice[y + j][x + k - 1 - i] = temp[i][j]

 

2. 가장 큰 덩어리 찾기

남아있는 얼음 중 가장 큰 덩어리가 차지하는 칸의 개수를 구하기 위해서는 DFS 또는 BFS를 사용하여야 한다.

나는 그 둘을 사용해본 적이 없었기에, 공부 후 두 가지 코드를 전부 작성해보았다.

 

(1) BFS

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

visited = [[False for _ in range(grid)] for _ in range(grid)]

def BFS(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    ans = 1

    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < grid and 0 <= nx < grid and ice[ny][nx] > 0 and not visited[ny][nx]:
                ans += 1
                visited[ny][nx] = True
                q.append((ny, nx))

    return ans

 

(2)  DFS

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

visited = [[False for _ in range(grid)] for _ in range(grid)]

def DFS(y, x):
    visited[y][x] = True
    ans = 1

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < grid and 0 <= nx < grid and ice[ny][nx] > 0 and not visited[ny][nx]:
            ans += DFS(ny, nx)
    
    return ans

 

BFS와 DFS의 정의, 차이점과 각각의 구현 방법에 대해서는 너무너무 중요하기 때문에 따로 글을 작성해야겠다. 🔥

2022.07.02 - [Algorithm] - BFS와 DFS의 개념, 차이점과 구현(Python)

 

 

그리고 DFS을 사용했을 때 백준에서 계속 런타임 에러(RecursionError)가 나길래 보니까

백준 채점 서버에서 정해진 최대 재귀 깊이를 벗어나기 때문이라고 한다.

 

아래 코드를 추가해주니 맞았다고 떴다 ㅠㅠ

sys.setrecursionlimit(10000)

 

 

코드

---

(1) BFS

import sys
from collections import deque

N, Q = map(int, sys.stdin.readline().split())

grid = 2 ** N
ice = []  # 2^N X 2^N 격자
for _ in range(grid):
    ice.append(list(map(int, sys.stdin.readline().split())))

level = list(map(int, sys.stdin.readline().split()))  # 단계 L

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

for L in level:
    k = 2 ** L

    # 부분 격자 시작 좌표 (y, x)
    for y in range(0, grid, k):
        for x in range(0, grid, k):
            # 부분 격자 복사
            temp = [ice[i][x:x + k] for i in range(y, y + k)]

            # 회전
            for i in range(k):
                for j in range(k):
                    ice[y + j][x + k - 1 - i] = temp[i][j]

    # 녹아야 하는 얼음 찾기
    melt = []
    for y in range(grid):
        for x in range(grid):
            if ice[y][x] > 0:
                check = 0
                for i in range(4):
                    check_y = y + dy[i]
                    check_x = x + dx[i]
                    if 0 <= check_y < grid and 0 <= check_x < grid:
                        if ice[check_y][check_x] != 0:
                            check += 1
                if check < 3:
                    melt.append([y, x])

    # 얼음 융해
    for m_y, m_x in melt:
        ice[m_y][m_x] -= 1

visited = [[False for _ in range(grid)] for _ in range(grid)]


def BFS(y, x):
    q = deque()
    q.append((y, x))
    visited[y][x] = True
    ans = 1

    while q:
        y, x = q.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < grid and 0 <= nx < grid and ice[ny][nx] > 0 and not visited[ny][nx]:
                ans += 1
                visited[ny][nx] = True
                q.append((ny, nx))

    return ans


left_ice = 0  # 남아있는 얼음의 합
mte = 0  # 가장 큰 얼음 뭉탱이
for y in range(grid):
    for x in range(grid):
        if ice[y][x] > 0:
            left_ice += ice[y][x]
            if not visited[y][x]:
                mte = max(mte, BFS(y, x))
print(left_ice)
print(mte)

 

(2) DFS

import sys

sys.setrecursionlimit(10000)

N, Q = map(int, sys.stdin.readline().split())

grid = 2 ** N
ice = []  # 2^N X 2^N 격자
for _ in range(grid):
    ice.append(list(map(int, sys.stdin.readline().split())))

level = list(map(int, sys.stdin.readline().split()))  # 단계 L

dy = (-1, 0, 1, 0)
dx = (0, 1, 0, -1)

for L in level:
    k = 2 ** L

    # 부분 격자 시작 좌표 (y, x)
    for y in range(0, grid, k):
        for x in range(0, grid, k):
            # 부분 격자 복사
            temp = [ice[i][x:x + k] for i in range(y, y + k)]

            # 회전
            for i in range(k):
                for j in range(k):
                    ice[y + j][x + k - 1 - i] = temp[i][j]

    # 녹아야 하는 얼음 찾기
    melt = []
    for y in range(grid):
        for x in range(grid):
            if ice[y][x] > 0:
                check = 0
                for i in range(4):
                    check_y = y + dy[i]
                    check_x = x + dx[i]
                    if 0 <= check_y < grid and 0 <= check_x < grid:
                        if ice[check_y][check_x] != 0:
                            check += 1
                if check < 3:
                    melt.append([y, x])

    # 얼음 융해
    for m_y, m_x in melt:
        ice[m_y][m_x] -= 1

visited = [[False for _ in range(grid)] for _ in range(grid)]


def DFS(y, x):
    visited[y][x] = True
    ans = 1

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < grid and 0 <= nx < grid and ice[ny][nx] > 0 and not visited[ny][nx]:
            ans += DFS(ny, nx)

    return ans


left_ice = 0  # 남아있는 얼음의 합
mte = 0  # 가장 큰 얼음 뭉탱이
for y in range(grid):
    for x in range(grid):
        if ice[y][x] > 0:
            left_ice += ice[y][x]
            if not visited[y][x]:
                mte = max(mte, DFS(y, x))
print(left_ice)
print(mte)

 

이 문제를 풀면서 중요한 내용들을 정말 많이 접한 것 같다. 오늘 공부한 내용들을 잊지 않도록 해야겠다.