[백준] 21610 - 마법사 상어와 비바라기 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

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

 

이 문제는 구현 문제입니다.

 

입력으로 NXN 배열에 저장된 값이 주어지고, 주어진 문제 조건대로 명령을 수행한 후 마지막에 NXN 배열에 저장된 값의 합을 구하는 것이 이 문제의 목표입니다.

 

접근 방식

1. 입력 값을 입력받기

2. 초기 구름의 위치 정보를 1차원 배열인 cloud_list와 2차원 배열인 cloud_mat에 저장

cloud_list: 구름의 위치 정보(행, 열 값) 저장한 리스트로 구름을 이동시키는 연산을 편하게 하기 위해 사용됨
cloud_mat: 구름이 있는 위치는 True, 없는 위치는 False로 저장한 2차원 리스트로 새로운 구름을 생성하는 연산을 편하게 하기 위해 사용됨

 

3. 현재 cloud_list에 있는 구름을 이동 주어진 방향으로 이동시킨 후 cloud_list와 cloud_mat을 업데이트

문제에서 주어진 NXN 격자는 1번 행과 N번 행, 1번 열과 N번 열이 연결된 상태이므로,
구름을 이동할 때 아래와 같은 식을 따름

(새로운 행 위치) = ((현재 행 위치) + (이동할 방향) * (이동할 거리)) % N

 

4. 현재 cloud_list에 저장된 구름 위치에 비를 내림(값 1 증가)

 

5. 비가 내린 위치 주변 대각선 위치에 물이 저장됐다면, 그 칸의 개수만큼 추가적으로 값 증가

 

6. 바구니에 물의 양이 2 이상인 위치에 구름 생성

cloud_mat을 이용하면 해당 기능을 O(N^2)으로 구현 가능

 

7. 명령문이 끝날 때까지 3 ~ 6을 반복

 

전체 코드

제출 언어: PyPy3

시간: 184ms

import sys

def move(d, s):
    global N, dy, dx, cloud_mat, cloud_list

    for i in range(len(cloud_list)):
        cr, cc = cloud_list[i]

        nr, nc = (cr+dy[d-1]*s) % N, (cc+dx[d-1]*s) % N
        cloud_list[i] = (nr, nc)

    for cloud in cloud_list:
        cr, cc = cloud

        cloud_mat[cr][cc] = True

def increase_water():
    global mat, cloud_list

    for cloud in cloud_list:
        cr ,cc = cloud

        mat[cr][cc] += 1

def increase_extra_water():
    global N, mat, dy, dx, cloud_list

    for cloud in cloud_list:
        cr, cc = cloud
        extra_water = 0

        for i in range(1, 8, 2):
            nr, nc = cr+dy[i], cc+dx[i]

            if 0 <= nr < N and 0 <= nc < N and mat[nr][nc] > 0:
                extra_water += 1

        mat[cr][cc] += extra_water

def create_cloud():
    global N, mat, cloud_mat, cloud_list

    total = 0
    temp_cloud = []

    for i in range(N):
        for j in range(N):

            if cloud_mat[i][j]:
                cloud_mat[i][j] = False
            
            elif not cloud_mat[i][j] and mat[i][j] >= 2:
                mat[i][j] -= 2
                temp_cloud.append([i, j])
            
            total += mat[i][j]

    cloud_list = temp_cloud

    return total

if __name__ == "__main__":
    N, M = map(int, sys.stdin.readline().strip().split())

    mat = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(N) ]
    command_list = [ list(map(int, sys.stdin.readline().strip().split())) for _ in range(M) ]

    dy, dx = [0, -1, -1, -1, 0, 1, 1, 1], [-1, -1, 0, 1, 1, 1, 0, -1]
    
    cloud_list = [(N-2, 0), (N-2, 1), (N-1, 0), (N-1, 1)]
    cloud_mat = [ [ False ] * N for _ in range(N) ]
    
    answer = 0
    
    for command in command_list:
        d, s = command
        
        move(d, s)

        increase_water()

        increase_extra_water()

        answer = create_cloud()

    print(answer)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊