[ Baekjoon - 10/12 ] - 21610번: 마법사 상어와 비바라기

• 문제 링크 : https://www.acmicpc.net/problem/21610

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

 

• 소요 시간 : 1시간 반

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 1024MB
   • 문제
     
     • NxN의 지도(2≤N≤50), M개의 이동정보(1≤M≤100)
     • 이동정보 : 갈수있는 방향 수 d(1≤d≤8), 한번에 갈수있는 칸수 si(1≤si≤50)
     • 문제에서 주어진 5개의 절차를 수행할 때, 지도에 남은 물의양의 합을 출력하는 문제
   • 이해
     • 문제가 길어서 처음봤을때 이해가 난해할 수 있지만, 사실상 진행 순서가 딱딱 주어진 문제라서 그대로 하나하나 구현하면 되는 문제이다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 처음에 각 격자 기본형태 뿐만아니라, 1번행과 N번째행 그리고 1번열과 N번열이 연결되어있다는 조건때문에 이해가 어려웠던것 같다.
   • 큰 형태를 이해하고 문제에서 주어진 절차들을 다시 써보면서 이해하려 했다.
3. 문제를 어떻게 해결할 것인가
   • • 위 문제는 이미 절차를 주었기 때문에 해당 절차에 어떤식으로 구현할지만 생각하면 되는 문제라 생각했다.
     • 1. 모든 구름이 di 방향으로 si칸 이동한다.
       • 지도의 칸을 di 방향으로 si만큼 더하여 이동한다.
       • 지도 전체를 옮겨도 되지만, 좀 더 효율적으로 작동하게 하기 위해서는 구름이 있는 좌표만 이동연산을 하면된다.
     • 2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
       • 구름이 있는 구역의 바구니의 물의양을 +1을 한다 (반복문 순회)
     • 3.구름이 모두 사라진다.
       • 구름을 저장한 배열이나 리스트를 초기화하면된다.
     • 4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
       • 대각선 방향으로 좌표를 이동했을때 물이 존재한다면 cnt+=1연산을 반복한다.
       • 그리고 이를 원래좌표의 물의 양에 더한다.
     • 5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
       • 구름을 저장할 변수를 하나 더 선언하고(과거/현재 차이임) 과거 구름이 있었던 자리 제외하고 물의 양이 2이상인 칸에 구름을 생성하고 물을 2 감소한다.
4. 위 계획을 검증
   • 문제에서 주어진대로 따라간거라 코드에서 오류가 나지않는 이상 논리에는 오류가 없다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main {
            static int N,M;
            static int[][] map;
            static boolean[][] res_cloud, cur_cloud;
            static int[] dx={0,-1,-1,-1,0,1,1,1}, dy={-1,-1,0,1,1,1,0,-1};
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                StringTokenizer st = new StringTokenizer(br.readLine());
        
                N = Integer.parseInt(st.nextToken());
                M = Integer.parseInt(st.nextToken());
        
                map = new int[N][N];
                for (int ni = 0; ni < N; ni++) {
                    st = new StringTokenizer(br.readLine());
                    for (int nj = 0; nj < N; nj++) {
                        map[ni][nj] = Integer.parseInt(st.nextToken());
                    }
                }
        
                res_cloud = new boolean[N][N];
                res_cloud[N-2][0] = true;
                res_cloud[N-2][1] = true;
                res_cloud[N-1][0] = true;
                res_cloud[N-1][1] = true;
        
                while(M-->0){
                    // 0. 구름지우기
                    cur_cloud = new boolean[N][N];
                    st = new StringTokenizer(br.readLine());
                    int d = Integer.parseInt(st.nextToken())-1;
                    int s = Integer.parseInt(st.nextToken());
        
                    // 1. 구름이동
                    for (int ni = 0; ni < N; ni++) {
                        for (int nj = 0; nj < N; nj++) {
                            int nx=ni;
                            int ny=nj;
                            for (int si = 0; si < s; si++) {
                                int x = nx+dx[d];
                                int y = ny+dy[d];
                                nx = x<0?N+x:(x>=N?x-N:x);
                                ny = y<0?N+y:(y>=N?y-N:y);
                            }
                            if(res_cloud[ni][nj]){
                                cur_cloud[nx][ny] = res_cloud[ni][nj];
                                // 2. 구름이 있는 칸의 바구니 물 양 1증가
                                map[nx][ny]+=1;
                            }
                        }
                    }
        
                    // 3번(구름지우기)은 5번의(~는 구름이 사라진 칸이 아니어야한다)의 조건을 따지기 위해 후에(0번때) 지움
        
                    // 4. 대각선 방향에 물이 있다면 구름이 있었던 칸의 물 양 +
                    for (int ni = 0; ni < N; ni++) {
                        for (int nj = 0; nj < N; nj++) {
                            if(cur_cloud[ni][nj]){
                                // 대각선 칸은 dx,dy의 1,3,5,7 번째 칸
                                int cnt=0;
                                if(0<=ni+dx[1] && ni+dx[1]<N && 0<=nj+dy[1] && nj+dy[1]<N)
                                    if(map[ni+dx[1]][nj+dy[1]]>0)
                                        cnt+=1;
                                if(0<=ni+dx[3] && ni+dx[3]<N && 0<=nj+dy[3] && nj+dy[3]<N)
                                    if(map[ni+dx[3]][nj+dy[3]]>0)
                                        cnt+=1;
                                if(0<=ni+dx[5] && ni+dx[5]<N && 0<=nj+dy[5] && nj+dy[5]<N)
                                    if(map[ni+dx[5]][nj+dy[5]]>0)
                                        cnt+=1;
                                if(0<=ni+dx[7] && ni+dx[7]<N && 0<=nj+dy[7] && nj+dy[7]<N)
                                    if(map[ni+dx[7]][nj+dy[7]]>0)
                                        cnt+=1;
                                map[ni][nj]+=cnt;
                            }
                        }
                    }
        
                    // 5. 바구니에 저장된 물의양이 2이상인 모든 칸에 구름생성 및 물의양 2 감소
                    res_cloud = new boolean[N][N];
                    for (int ni = 0; ni < N; ni++) {
                        for (int nj = 0; nj < N; nj++) {
                            // 물의양이 2이상 그리고 전에 구름이 있었던칸이 아님 -> 가능
                            if(!cur_cloud[ni][nj] && map[ni][nj]>=2){
                                res_cloud[ni][nj] = true;
                                map[ni][nj]-=2;
                            }
                        }
                    }
                }
                int ans=0;
                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        ans+=map[i][j];
                    }
                }
                System.out.println(ans);
            }
        }

   2. Python 3

      • import sys
        input = sys.stdin.readline
        
        N, M = map(int, input().split())
        graph = [list(map(int, input().split())) for _ in range(N)]
        res_cloud = [[N - 2, 0], [N - 2, 1], [N - 1, 0], [N - 1, 1]]
        
        dx = [0, -1, -1, -1, 0, 1, 1, 1]
        dy = [-1, -1, 0, 1, 1, 1, 0, -1]
        for m in range(M):
            # 1. 구름이동
            next_clouds = []
            d, s = map(int, input().split())
            d -= 1
            for cloud in res_cloud:
                x = cloud[0]
                y = cloud[1]
                nx = (N + x + dx[d] * s) % N
                ny = (N + y + dy[d] * s) % N
                next_clouds.append([nx, ny])
        
            # 2. 구름이 있는 칸의 바구니 물 양 1증가
            visited = [[False] * N for _ in range(N)]
            for cloud in next_clouds:
                x = cloud[0]
                y = cloud[1]
                graph[x][y] += 1
                visited[x][y] = True
        
            # 3. 구름 지우기
            res_cloud = []
        
            # 4. 대각선 방향에 물이 있다면 구름이 있었던 칸의 물 양 +
            dxy=[1,3,5,7]
            for cloud in next_clouds:
                x = cloud[0]
                y = cloud[1]
                cnt = 0
                for i in range(4):
                    idx = (i+1)*2-1
                    nx = x + dx[idx]
                    ny = y + dy[idx]
                    if 0 <= nx < N and 0 <= ny < N and graph[nx][ny] >= 1:
                        cnt += 1
                graph[x][y] += cnt
        
            # 5. 바구니에 저장된 물의양이 2이상인 모든 칸에 구름생성 및 물의양 2 감소
            for i in range(N):
                for j in range(N):
                    if graph[i][j] >= 2 and visited[i][j] == False:
                        graph[i][j] -= 2
                        res_cloud.append([i, j])
        
        ans = 0
        for i in range(N):
            ans += sum(graph[i])
        
        print(ans)

 

 

• 결과 - Java11코드를 그대로 Python3으로 치환했을때 시간초과가 발생했다. 확실히 파이썬 깐깐함..