[python] BOJ 백준 21610: 마법사상어와 비바라기

1. 문제  

마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 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번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

2. 입력   

첫째 줄에 N, M이 주어진다.

둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.

다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

3. 출력   

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

4. 해결방법   

이 문제는 구현, 시뮬레이션 문제이다. 구름배열과 바구니 격자배열을 계속해서 업데이트 해주면서 각 단계를 진행하면된다. 다만 각 단계에서 구름이 이미 생성된 칸에 대해서 정보를 계속해서 가지고 있어야하므로 방문배열 visited를 생성해서 관리를 해주어야한다. 기존 배열에서 들어있는지를 확인하는 in 함수를 쓰게된다면 O(n)의 시간이 걸려서 시간초과가 일어나게되기 때문이다.  

1) move함수: 방향 d에 대해서 s만큼 이동한다. 다만 행과열을 각각 이어져있다고 하였으므로 범위가 넘어가다면 각 끝점으로 다시 이어주어야한다. 또한 여기서 방문체크를 해주는 배열을 같이 계산하여 리턴을 해주어야 5단계의 구름생성에서 활용할 수 있다. 

2) rain 함수: 구름이 있는 곳에 대해서 물의 양을 1씩 증가시켜준다. 그 후에 물복사를 실시하여 대각선을 탐색해준다. 이때 임시배열을 만들고 증가시킬 물의양을 따로 저장해주어야 계산오류가 나지않는다. 한번에 적용시켜준다면 동시성에 어긋나므로 계산오류가 일어나게 된다. 

3) make_cloud 함수: 물이 2이상이고 move함수에서 리턴한 방문배열에서 체크가 안되어있다면 구름이 생성가능한 부분이다. 새로운 배열에 저장해주고 리턴해준다음, 메인함수에서 원래의 구름배열에 저장해주면된다. 

 

5) 구현코드   

n,m=map(int,input().split())
a=[list(map(int,input().split()))for _ in range(n)] #격자 
commands=[list(map(int,input().split())) for _ in range(m)] #명령
cloud=[(n-1,0),(n-1,1),(n-2,0),(n-2,1)] #구름배열 

#8가지 방향 
dx=[0,-1,-1,-1,0,1,1,1]
dy=[-1,-1,0,1,1,1,0,-1]

#1단계: 구름이동 
def move(d,s):
  #5단게를 위해 저장할 방문여부 배열 
  visited=[[0]*n for _ in range(n)]
  d-=1 #방향 
  for i in range(len(cloud)):
    x,y=cloud[i] #구름좌표 
    for _ in range(s): #s만큼이동 
      x,y=x+dx[d],y+dy[d]
      #경계를 넘어가는건 이어주기 
      if x<0: x=n-1
      if x>=n: x=0
      if y<0: y=n-1
      if y>=n : y=0 
    cloud[i]=(x,y) #구름좌표 업데이트 
    visited[x][y]=1 #방문체크 
  return visited #방문배열 리턴 

#2,4단계: 물증가, 물복사버그 
def rain():
  temp=[]
  #2단계: 비오기 
  for x,y in cloud:
    a[x][y]+=1#물증가 

  #4단계: 물복사마법 실시   
  for x,y in cloud:
    cnt=0 #대각선 물개수  
    for i in [1,3,5,7]: #대각선 
      nx,ny=x+dx[i],y+dy[i] 
      if 0<=nx<n and 0<=ny<n:#범위안 
        if a[nx][ny]>0: #물있으면 
          cnt+=1 #개수증가 
    temp.append((x,y,cnt)) #임시배열에 저장 
  for x,y,cnt in temp:
      a[x][y]+=cnt #물복사

#3,5단게: 새로운 구름생성 
def make_cloud(cloud,visited):
  temp=[] #새로운 구름배열 
  for i in range(n):
    for j in range(n):
      #물이 2이상이고 예전에 구름이 아닌칸
      if a[i][j]>=2 and visited[i][j]==0:
        temp.append((i,j)) #구름생성 
        a[i][j]-=2 #물의양 줄기 
  return temp 


for d,s in commands:
  visited=move(d,s) 
  rain()
  cloud=make_cloud(cloud,visited)

answer=0
for i in range(n):
  answer+=sum(a[i])
print(answer)

 

⭐️난이도:  골드 5 ⭐️

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

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