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

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

21610번: 마법사 상어와 비바라기

1. 무한 격자!

"마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다."

 

지난번에 풀이했던 백준 20056 : 마법사 상어와 파이어볼에서 나왔던 것과 같다. 격자가 무한히 펼쳐져 있기 때문에 범위를 벗어날 경우에 경계 안쪽으로 넣어주면 된다. 그리고 방문처리 함수를 두어서 매 턴마다 비가 내렸던 지역을 방문처리해준다. 이렇게 하면 마지막에 구름 생성할 때, 이전에 구름이 있었던 위치는 포함 안 할 수 있다.

 

※ 코드 내 정의된 함수

구름 이동 함수 : moveNrain()

물복사 버그 함수 : copybug()

구름 생성 함수 : cloud()

2. 전체 코드

메모리 : 118116 KB, 시간 : 268 ms, 풀이 시간 : 60 min

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
water_info = [[N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]]
ds_info = [list(map(int, input().split())) for _ in range(M)]

dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]

def moveNrain():
    temp = []
    di, si = ds_info[0]
    del ds_info[0]
    while water_info :
        x, y = water_info[0]
        del water_info[0]
        nx = x + si * dx[di]
        ny = y + si * dy[di]
        while nx < 0 : nx += N
        while nx >= N : nx -= N
        while ny < 0 : ny += N
        while ny >= N : ny -= N
        board[nx][ny] += 1
        visited[nx][ny] = True
        temp.append([nx, ny])
    return temp

def copybug():
    while water_info :
        x, y = water_info[0]
        del water_info[0]
        cnt = 0
        for d in [2, 4, 6, 8] :
            nx = x + dx[d]
            ny = y + dy[d]
            if 0 <= nx < N and 0 <= ny < N and board[nx][ny] > 0 :
                cnt += 1
        board[x][y] += cnt

def cloud():
    temp = []
    for i in range(N):
        for j in range(N):
            if board[i][j] >= 2 and not visited[i][j] :
                board[i][j] -= 2
                temp.append([i, j])
    return temp

it = 0
while it < M :
    visited = [[False for _ in range(N)] for _ in range(N)]
    water_info = moveNrain()
    water_info = copybug()
    water_info = cloud()
    it += 1
result = 0
for i in range(N) :
    result += sum(board[i])

print(result)