[백준] 21610. 마법사 상어와 비바라기 (Python)

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

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

 

✏️ 구름이 이동할 땐 첫번째 행,열과 마지막 행,열이 연결되어 있지만 대각선에 바구니를 확인할 땐 연결되어 있지 않다는 것을 잘 생각해야 하는 문제였다.

✏️ 처음 푼 코드로는 시간초과가 났다. 구름이 사라진 칸인지 확인하는 과정에서 not in을 썼는데, 이를 배열을 하나 만들어 체크해주는 식으로 바꾸어 시간초과를 해결했다. 

 

📌 시간초과 난 코드

import sys
input = sys.stdin.readline

def movCloud(lst, direction, count):
    for idx in range(len(lst)):
        for num in range(2):
            lst[idx][num] += dir[direction][num]*(count%N)
            if lst[idx][num] >= N:
                lst[idx][num] = lst[idx][num]%N
            elif lst[idx][num] < 0:
                lst[idx][num] = lst[idx][num]+N
    return lst

def checkDgs(y, x):
    isWater = 0
    checkDir = [(-1, -1), (-1, 1), (1, 1), (1, -1)]
    for i, j in checkDir:
        dy, dx = y+i, x+j
        if 0 <= dy < N and 0 <= dx < N:
            if board[dy][dx] > 0:
                isWater += 1
    return isWater

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move = [list(map(int, input().split())) for _ in range(M)] # 방향, 거리
dir = [(0, 0), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)] # 8방향
cloud = [[N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]]

for idx in range(M):
    clound = movCloud(cloud, move[idx][0], move[idx][1])
    for y, x in clound:
        board[y][x] += 1
    for y, x in cloud:
        board[y][x] += checkDgs(y, x)
    newCloud = []
    for y in range(N):
        for x in range(N):
            if board[y][x] >= 2 and [y, x] not in cloud:
                newCloud.append([y, x])
                board[y][x] -= 2
    cloud = newCloud

res = 0

for idx in range(N):
    res += sum(board[idx])

print(res)

 

 

📌 정답 코드

import sys
input = sys.stdin.readline

def movCloud(lst, direction, count):
    for idx in range(len(lst)):
        for num in range(2):
            lst[idx][num] += dir[direction][num]*(count%N) # if count가 50이고 N이 5이면 움직일 필요 X
            if lst[idx][num] >= N: # 처음과 끝이 연결되어 있으므로 N이상일 경우 처리
                lst[idx][num] = lst[idx][num]%N
            elif lst[idx][num] < 0: # 동일한 이유로 음수일 때 처리
                lst[idx][num] = lst[idx][num]+N
    return lst

def checkDgs(y, x): # 대각선 중 바구니에 물 있는 개수 구하기
    isWater = 0
    checkDir = [(-1, -1), (-1, 1), (1, 1), (1, -1)]
    for i, j in checkDir:
        dy, dx = y+i, x+j
        if 0 <= dy < N and 0 <= dx < N:
            if board[dy][dx] > 0:
                isWater += 1
    return isWater

N, M = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)]
move = [list(map(int, input().split())) for _ in range(M)] # 방향, 거리
dir = [(0, 0), (0, -1), (-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1)] # 8방향
cloud = [[N-1, 0], [N-1, 1], [N-2, 0], [N-2, 1]] # 초기 구름 위치

for idx in range(M):
    clound = movCloud(cloud, move[idx][0], move[idx][1]) # 구름 움직여주기
    checkCloud = [[0]*N for _ in range(N)] # 구름 있는 곳 체크 용도
    for y, x in clound:
        board[y][x] += 1 # 구름 있는 칸 바구니에 물 +1
        checkCloud[y][x] = 1 # 구름 있다고 체크
    for y, x in cloud:
        board[y][x] += checkDgs(y, x) # 대각선에 물 있는 수만큼 물 증가
    newCloud = []
    for y in range(N):
        for x in range(N):
            if board[y][x] >= 2 and checkCloud[y][x] == 0: # 바구니에 물이 2 이상 있고, 구름 있던 칸이 아니면
                newCloud.append([y, x]) # 새로운 구름 칸으로 추가
                board[y][x] -= 2 # 물 2 감소
    cloud = newCloud # 구름 리스트 교체

res = 0

for idx in range(N):
    res += sum(board[idx]) # 각 행마다 물의 양 더해주기

print(res)