백준 21610: 마법사 상어와 비바라기 - 구현, 시뮬레이션 (파이썬, 자바)

마법사 상어와 비바라기 성공

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번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.

제한

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

 

 

내 코드

import sys

#이동한 위치에서 구름 만들기
def newCloud():
    global visited
    l=len(cloud) #이전 구름 개수를 저장.

    for i in range(n):
        for j in range(n):
            if arr[i][j]>1 and not visited[i][j]: #visited를 통해 이전 구름을 제외
                arr[i][j]-=2
                cloud.append([i,j])

    #이전의 구름들 제거
    for _ in range(l):
        cloud.pop(0)


#구름 근처 4방향 대각선에서 물 복사
def cloudEffect():
    for i in range(len(cloud)):
        x=cloud[i][0]
        y=cloud[i][1]
        for j in range(4):
            nx=x+cx[j]
            ny=y+cy[j]

            if nx<0 or nx>=n or ny<0 or ny>=n:
                continue
            if arr[nx][ny]>0:
                arr[x][y]+=1
        

#구름을 이동하고 비 내리기
def cloudMoveAndRain(d,s):

    #구름에서 비를 내리고 다음 구름 후보가 되지않기 위해 방문 배열 도입.
    global visited
    visited=[[False]*n for _ in range(n)]

    #구름 이동
    for i in range(len(cloud)):
        mx,my=move(cloud[i][0],cloud[i][1],d,s)
        cloud[i][0]=mx
        cloud[i][1]=my

    #이동한 구름에서 각각 1씩 비 내리기+방문 처리
    for x,y in cloud:
        arr[x][y]+=1
        visited[x][y]=True
    
    
#이동 로직(범위에 따라 조정)
def move(x,y,d,s):
    nx=x
    ny=y

    #x,y좌표를 이동 -> nx,ny
    for _ in range(s):
        nx+=dx[d-1]
        ny+=dy[d-1]
    
    #nx가 범위내에 들어가도록 조정.
    while not (0<=nx<n):
        if nx<0:
            nx+=n
        elif nx>=n:
            nx-=n
    
    #ny가 범위내에 들어가도록 조정.
    while not (0<=ny<n):
        if ny<0:
            ny+=n
        elif ny>=n:
            ny-=n
        
    return nx,ny #이동한 구름의 x,y 좌표 리턴


#메인 코드 부분
n,m=map(int,sys.stdin.readline().split())

arr=[]
for _ in range(n):
    arr.append(list(map(int,sys.stdin.readline().split())))


command=[]
for _ in range(m):
    command.append(list(map(int,sys.stdin.readline().split())))


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

#비바라기용 방향 체크
cx=[-1,-1,1,1]
cy=[-1,1,-1,1]

#초기 구름 위치
cloud=[[n-2,0],[n-2,1],[n-1,0],[n-1,1]]

for i in range(m):
    cloudMoveAndRain(command[i][0],command[i][1])
    cloudEffect() #물 복사
    newCloud()

answer=0
for x in arr:
    answer+=sum(x)

print(answer)

 

풀이 및 접근)

- 이 문제는 시키는대로만 잘 수행하면 잘 풀리는 문제이다. 구현하는데 약간의 복잡함이 있어서 시간이 어느정도 걸렸다.

- 신경써야할 부분은 구름이 이동할 때이다. 구름의 좌표가 범위 밖을 넘어가면 문제의 조건에 따라 조정을 해주어야 한다. 위 코드에서는 좌표가 0보다 작거나 최대 크기를 벗어나면 길이만큼 더해주거나 빼서 좌표를 조정하였다. 하지만 이 방식보다 모듈러(%) 연산을 통해 조정하는 것이 더 간단한 방법인 것 같다. (참고)

- 또한 이전에 구름이었던 좌표들을 다음 구름 후보에 들지않게 하기 위해 visited를 도입하였다. 이를 도입하지 않고,

    if [x,y] in cloud:

를 통해서 일일이 비교하였더니 시간초과가 났다. 이를 해결하기 위해 visited로 대체하였더니 해결되었다.

- 어렵진 않지만 구현력을 기를 수 있는 문제였다.

 

 

자바 ver.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n;
    static int m;
    static boolean[][] visited;
    static int[][] arr;
    static int[] dx={0,-1,-1,-1,0,1,1,1};
    static int[] dy={-1,-1,0,1,1,1,0,-1};

    static int[] cx={-1,-1,1,1};
    static int[] cy={-1,1,-1,1};

    static List<int[]> command=new ArrayList<>();
    static List<int[]> cloud=new ArrayList<>();


    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        String input[]=br.readLine().split(" ");
        n=Integer.parseInt(input[0]);
        m=Integer.parseInt(input[1]);

        arr=new int[n][n];

        for(int i=0; i<n; i++){
            String[] tmp=br.readLine().split(" ");
            for(int j=0; j<n; j++){
                arr[i][j]=Integer.parseInt(tmp[j]);
            }
        }

        visited=new boolean[n][n];


        for(int i=0; i<m; i++){
            String[] s = br.readLine().split(" ");
            int[] tmp={Integer.parseInt(s[0]),Integer.parseInt(s[1])};
            command.add(tmp);
        }

        cloud.add(new int[]{n-2,0});
        cloud.add(new int[]{n-2,1});
        cloud.add(new int[]{n-1,0});
        cloud.add(new int[]{n-1,1});

        for(int i=0; i<m; i++){
            cloudMoveAndRain(command.get(i)[0],command.get(i)[1]);
            cloudEffect();
            newCloud();
        }

        int answer=0;

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                answer+=arr[i][j];
            }
        }
        System.out.println(answer);


    }

    private static void newCloud() {
        int l = cloud.size();

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(arr[i][j]>1 && !(visited[i][j])){
                    arr[i][j]-=2;
                    cloud.add(new int[] {i,j});
                }
            }
        }

        for(int i=0; i<l; i++){
            cloud.remove(0);
        }
    }

    private static void cloudEffect() {
        for(int i=0; i<cloud.size(); i++){
            int x=cloud.get(i)[0];
            int y=cloud.get(i)[1];
            for(int j=0; j<4; j++){
                int nx=x+cx[j];
                int ny=y+cy[j];

                if(nx<0 || nx>=n || ny<0 || ny>=n){
                    continue;
                }
                if(arr[nx][ny]>0){
                    arr[x][y]+=1;
                }
            }
        }
    }


    private static void cloudMoveAndRain(int d, int s) {
        for(int i=0; i<n; i++) {
            Arrays.fill(visited[i], false);
        }

        for(int i=0; i<cloud.size(); i++){
            int[]pos;
            pos=move(cloud.get(i)[0],cloud.get(i)[1],d,s);
            cloud.get(i)[0]=pos[0];
            cloud.get(i)[1]=pos[1];
        }

        for (int[] ints : cloud) {
            int x=ints[0];
            int y=ints[1];
            arr[x][y]+=1;
            visited[x][y]=true;
        }
    }

    private static int[] move(int x, int y, int d, int s) {
        int nx=x;
        int ny=y;

        for(int i=0; i<s; i++){
            nx+=dx[d-1];
            ny+=dy[d-1];
        }

        while(!(0<=nx && nx<n)){
            if(nx<0){
                nx+=n;
            }
            else if(nx>=n){
                nx-=n;
            }
        }

        while(!(0<=ny && ny<n)){
            if(ny<0){
                ny+=n;
            }
            else if(ny>=n){
                ny-=n;
            }
        }

        return new int[] {nx,ny};
    }


}