99클럽 코테 스터디 21일차 TIL - [백준/파이썬] - 21610 마법사 상어와 비바라기

문제 출처 : https://www.acmicpc.net/problem/21610

 

격자 N * N에서 A[r][c]는 (r,c)에 저장된 물의 양을 의미한다. 

1번 행과 N번 행, 1번 열과 N번 열이 연결되어 있다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2) => (N-1, 0), (N-1, 1), (N-2, 0), (N-2, 1), 

 M번 명령. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

 

제한

• 2 ≤ N ≤ 50
• 1 ≤ M ≤ 100
• 0 ≤ A[r][c] ≤ 100
• 1 ≤ di ≤ 8
• 1 ≤ si ≤ 50

풀이

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
clst1 = [(N-1,0),(N-1,1),(N-2,0),(N-2,1)]   # 구름 초기 위치

di, dj = [0,0,-1,-1,-1,0,1,1,1],[0,-1,-1,0,1,1,1,0,-1]
for _ in range(M) : # M번 입력 받아서 반복 처리
    D, S = map(int, input().split())
    # [1] 구름 이동 [2] 물 증가 [3] 구름 사라짐(clst2에 좌표 저장)
    clst2 = []                  # 이동할 구름 위치(좌표) 저장
    for ci, cj in clst1 :
        ni, nj = (ci+di[D]*S+N)%N, (cj+dj[D]*S+N)%N # 양쪽 끝이 연결되어 있으므로
        arr[ni][nj] += 1        # [2] 물 증가
        clst2.append((ni, nj))

    # [2] 구름 이동한 위치에서 대각선 체크
    v = [[0]*N for _ in range(N)]
    for ci, cj in clst2 :
        v[ci][cj] = 1                   # 구름 위치 룩업 테이블에 표시
        for dii, djj in ((-1,-1),(-1,1),(1,-1),(1,1)) :
            ni, nj = ci + dii, cj + djj
            if 0<=ni<N and 0<=nj<N and arr[ni][nj] > 0 :
                arr[ci][cj] += 1

    # [3] 전체 순회 물 >= 2 인 자리 구름 발생(물 -= 2), 단 clst2 위치 제외
    clst1 = []
    for i in range(N) :
        for j in range(N) :
            # if arr[i][j] >= 2 and (i,j) not in clst2 :  # 500ms
            if arr[i][j] >= 2 and v[i][j] == 0 :  # 180ms
                arr[i][j] -= 2
                clst1.append((i, j))

ans = 0
for lst in arr :
    ans += sum(lst)
print(ans)

시뮬레이션

시뮬레이션 문제는 해도해도 적응이 되지 않는다. 많이 구현해보고 작성해보고 해봐야겠다.