[BOJ][Python] 백준 21610번 : 마법사 상어와 비바라기

- 문제 링크

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

- 풀이

백문 문제집에 있는 SW 역량 테스트 기출문제 중 하나이고, 악명(?) 높은 상어 문제 중 비교적 쉬운 편에 속하는 구현 + 시뮬레이션 문제였다. divide and conquer 방법으로 구현했다. 문제 하나를 더 작은 단위의 문제로 쪼개서 구현하는.. 그런 방법이다.

구름을 이동시키는 함수, 물복사버그 함수, 다시 구름을 만드는 함수 총 3개의 함수를 만들어서 사용했다. 함수 하나씩 차근차근히 살펴보자.

 

1. 구름 이동 함수

def move(x, y):
    queue = []
    while cloud:
        a, b = cloud.popleft()
        for i in range(y):
            a = a + dx[x]
            b = b + dy[x]
            
            if a >= N:
                a = 0
            elif a <= -1:
                a = N-1

            if b >= N:
                b = 0
            elif b <= -1:
                b = N-1
        queue.append((a, b))

    watercopy(queue)
    makecloud(queue)

먼저 구름을 이동시키는 move 함수다. 매개변수로 받은 x, y 값은 입력받은 방향과 거리 값이다. 자세히 보면 BFS 느낌과 비슷한 것을 볼 수 있다.

while cloud에서 나오는 cloud는 구름의 좌표값을 저장해놓은 deque이다. 

 

a >= N ... b >= N 부분은 문제를 보면 "1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다"고 했기 때문에 값이 범위를 넘어갔을 때 끝과 끝으로 연결해준다.

 

그리고 이동시킨 구름의 좌표값을 queue 배열에 넣어준 후 물복사버그 함수와 구름 만드는 함수를 실행시켜 준다.

 

2. 물복사버그 함수

def watercopy(queue):
    for i, j in queue:
        graph[i][j] += 1
    
    for k, l in queue:
        cnt = 0
        for z in range(1, 8, 2):
            nx = k + dx[z]
            ny = l + dy[z]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] > 0:
                    cnt += 1
            
        graph[k][l] += cnt

구름에 있는 칸에 비가 내려서 값이 1씩 추가되는 기능을 watercopy 함수에 구현했다.. 사실 move 함수에 구현하는 게 맞다..

밑의 for문에서는 각 대각선 방향에 물이 있는 갯수만큼 값을 추가해주었다. 

 

3. 구름 만드는 함수

def makecloud(queue):
    for i in range(N):
        for j in range(N):
            if graph[i][j] >= 2 and (i, j) not in queue:
                graph[i][j] -= 2
                cloud.append((i, j))

전체 격자 칸을 순회하며 값이 2보다 크면서  바로 전의 구름을 만들지 않은 격자 칸만 cloud에 삼입한다.

- 전체 코드

import sys
from collections import deque
input = sys.stdin.readline
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

def makecloud(queue):
    for i in range(N):
        for j in range(N):
            if graph[i][j] >= 2 and (i, j) not in queue:
                graph[i][j] -= 2
                cloud.append((i, j))

def move(x, y):
    queue = []
    while cloud:
        a, b = cloud.popleft()
        for i in range(y):
            a = a + dx[x]
            b = b + dy[x]
            
            if a >= N:
                a = 0
            elif a <= -1:
                a = N-1

            if b >= N:
                b = 0
            elif b <= -1:
                b = N-1
        queue.append((a, b))

    watercopy(queue)
    makecloud(queue)


def watercopy(queue):
    for i, j in queue:
        graph[i][j] += 1
    
    for k, l in queue:
        cnt = 0
        for z in range(1, 8, 2):
            nx = k + dx[z]
            ny = l + dy[z]
            if 0 <= nx < N and 0 <= ny < N:
                if graph[nx][ny] > 0:
                    cnt += 1
            
        graph[k][l] += cnt

N, M = map(int, input().split())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))
arr = []
for _ in range(M):
    a, b = map(int, input().split())
    arr.append((a, b))


cloud = deque()
cloud.append((N-1, 0))
cloud.append((N-1, 1))
cloud.append((N-2, 0))
cloud.append((N-2, 1))

for i, j in arr:
    move(i-1, j)

res = 0
for k in range(N):
    for l in range(N):
        res += graph[k][l]

print(res)

 

내가 생각해도 참.. 못짰다. ㅜㅜ 나중에 보면 와 내가 이걸 이렇게 짰다고 한탄할 정도로 별로다..

더 가독성 좋고 시간복잡도도 적은 코드를 짜기 위해 더 노력해야겠다 :)

추가적으로 위 코드는 python3으로 제출하면 시간 초과가 뜨고, pypy3으로 제출해야 시간 초과가 뜨지 않는다 !