[Baekjoon] 21610_마법사 상어와 비바라기

Gold V

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

---

<마법사 상어와 비바라기>

문제 

 

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전 하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A [r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

비바라기를 시전 하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 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번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

 

 

입력

 

첫째 줄에 N, M이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A [r][c]를 의미한다.
다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

 

출력 

 

첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

 

 

문제 풀이

 

 - my solution (Python)

 

import sys

n,m=map(int,sys.stdin.readline().split())
arr=[] # 바구니
cloud=[[0]*n for i in range(n)] # 구름
for i in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))

info=[] # 이동의 정보
for i in range(m):
    info.append(list(map(int,sys.stdin.readline().split())))

# 처음 비구름 위치
cloud[n-1][0]=1
cloud[n-1][1]=1
cloud[n-2][0]=1
cloud[n-2][1]=1

# 8개의 방향
dx=[0,-1,-1,-1,0,1,1,1]
dy=[-1,-1,0,1,1,1,0,-1]

# 대각선
dia_x=[-1,-1,1,1]
dia_y=[-1,1,-1,1]

for i in info:
    visited = [[0] * n for v in range(n)]
    for j in range(n):
        for k in range(n):
            if cloud[j][k]==1: # 비구름이 있다면 이동
                x=j+(dx[i[0]-1]*i[1])
                y=k+(dy[i[0]-1]*i[1])
                if x<0:
                    x=n-(-x)%n
                    if x==n:
                        x=0
                elif x>=n:
                    x%=n
                if y<0:
                    y = n - (-y) % n
                    if y==n:
                        y=0
                elif y>=n:
                    y%=n
                visited[x][y]=1 
                arr[x][y]+=1 # 비가 내려 구름 있는 칸의 물의 양 +1
                cloud[j][k]=0 # 구름이 사라짐
    for j in range(n): # 물복사버그
        for k in range(n):
            if visited[j][k]==1: # 물이 증가한 칸
                cnt=0
                for v in range(4): # 대각선
                    x=j+dia_x[v]
                    y=k+dia_y[v]
                    if 0<=x<n and 0<=y<n:
                        if arr[x][y]!=0:
                            cnt+=1
                arr[j][k]+=cnt # 물의 양 증가
    for j in range(n):
        for k in range(n):
            if arr[j][k]>=2 and visited[j][k]==0: # 물의 양 2 이상, 구름이 사라진 칸 x
                cloud[j][k]=1 # 구름 생김
                arr[j][k]-=2 # 물의 양 -2

result=0 # 바구니에 들어있는 물의 양의 합
for i in range(n):
    for j in range(n):
        result+=arr[i][j]

print(result)

 

• n, m 
• arr = N x N 격자 입력 저장
  info = 이동의 정보 입력 저장
• cloud = 구름 위치 정보 
  # 처음 비구름의 위치 (n-1,0) (n-1,1) (n-2,0) (n-2,1)
• dx, dy = 8 개의 방향
  dia_x, dia_y = 대각선
• 이동의 정보 리스트 순환 
  - visited = 구름이 사라진 칸 판별 및 물이 증가한 칸 판별
  
  # 문제에서 주어진 순서 3번까지 해결
  - arr 전체 순환하며 비구름이 있다면 di 방향으로 si 칸 이동 ( 1번 행과 N번 행, 1번 열과 N번 열을 연결했으므로 index를 잘 설정해주어야 한다. ) -> 이동한 칸 visited 1로 저장 및 비가 내리므로 구름이 있는 칸의 바구니에 저장된 물의 양 +1, 구름이 사라지므로 cloud 0으로 저장
  
  # 문제에서 주어진 순서 4번 해결
  - 물복사 버그를 위해 arr 전체 순환하여 물이 증가한 칸이라면 ( visited 값이 1이라면 ) 그 좌표에서 대각선을 구하여 그 arr 값이 0이 아니라면 cnt +1 -> 대각선 4곳을 판별한 후 arr (바구니)에 물의 양 증가해줌 (+cnt)
  
  # 문제에서 주어진 순서 5번 해결
  -  arr 전체를 순환하여 바구니에 들어있는 물이 2 이상이고 순서 3에서 구름이 사라진 칸이 아니라면 ( visited 값이 0이라면) 구름이 생기고 물의 양이 2 줄어듦
• result = 바구니에 들어있는 물의 양의 합
  - arr 전체를 순화하여 모든 값을 다 더해준 후 result 출력

 

 

❓ 왜 틀렸는가?

문제에서 주어진 예시만 생각해서 발생한 문제였다. 좌표를 구할 때 범위를 문제에서 제시한 값으로만 가능하도록 설정하여 틀렸습니다가 발생했다. 두 번째는 좌표를 구할 때 x, y 둘 다 예외 조건을 설정해야 하는데 x에만 설정하여 인덱스 에러가 발생한 것이었다.

 

 

❓ index 설정

1번 행과 N번 행을 연결하고, 1번 열과 N번 열을 연결했으므로 행과 열을 구할 때 조건식을 통하여 좌표를 구해주어야 한다.

혼자 좌표를 그려보면서 구한 식인데... 아직 글로 설명하기에는 힘든 것 같다...

다음에 정리해서 돌아오겠다 -!

 

---

생각🤔

 

문제를 잘 읽고 그대로 구현하면 해결할 수 있는 문제였다. 

하지만... 방심하지 말자... 하나라도 빠트리면 실패한다.

---