[백준(BOJ)] 21610번 : 마법사 상어와 비바라기 - PYTHON[파이썬]

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

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

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 구현
• 시뮬레이션

 

---

 

⊙ 문제 접근 과정

 

먼저 방향을 정의해준다.

 

그리고 큐에 구름 좌표를 넣고 반복문을 돌려준다.

구름 이동 후 1 증가 후 대각선을 체킹!

존재한다면 카운팅 후 더해준다.

 

마지막으로 물 양이 2 이상인지 체킹!

존재한다면 2 감소 후 큐에 추가.

 

---

 

⊙ 문제 풀이

 

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
dx = [0, -1, -1, -1, 0, 1, 1, 1]
dy = [-1, -1, 0, 1, 1, 1, 0, -1]

q = deque()
q.append([N-1, 0])
q.append([N-2, 0])
q.append([N-1, 1])
q.append([N-2, 1])

for _ in range(M):
    cloud = [[0] * N for _ in range(N)]
    d, s = map(int, input().split())
    while q:
        x, y = q.popleft()
        nx = (x + dx[d-1]*s) % N
        ny = (y + dy[d-1]*s) % N
        cloud[nx][ny] = 1

    for i in range(N):
        for j in range(N):
            if cloud[i][j] == 1:
                arr[i][j] += 1

    for i in range(N):
        for j in range(N):
            if cloud[i][j] == 1:
                x, y = i, j
                cnt = 0
                for k in [1, 3, 5, 7]:
                    nx = x + dx[k]
                    ny = y + dy[k]

                    if 0 <= nx < N and 0 <= ny < N:
                        if arr[nx][ny] > 0:
                            cnt += 1
                arr[x][y] += cnt

    for i in range(N):
        for j in range(N):
            if arr[i][j] >= 2 and cloud[i][j] == 0:
                arr[i][j] -= 2
                q.append([i, j])

s = 0
for i in range(N):
    s += sum(arr[i])

print(s)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

오랜만에 알고리즘 컴백. 그렇지만 어렵다.

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!