마법사 상어와 비바라기 - 백준(21610, 시뮬레이션)

🎯 마법사 상어와 비바라기

마법사 상어와 비바라기 - 21610, 시뮬레이션, 골드5


🧐 알고리즘[접근방법]

  1. 구름 위치가 저장되어 있는 배열 선언

  2. 주변(←, ↖, ↑, ↗, →, ↘, ↓, ↙) 이동 하는 배열 선언, 홀수일때 대각선으로 이동

  3. 구름 이동 하는 함수 구현(구역 초과 시 처음으로 이동)

  4. 물 증가하는 함수 구현

  5. 물 복사하는 함수 구현

  6. 구름 제거 후 구름 생성하는 함수 구현

  7. 전체 구역 물 개수 카운트 함수 구현


👨‍💻 소스

import java.util.*;

public class Main {
    static class Node {
        int x;
        int y;
        
        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    static int N; // 격자 크기
    static int M; // 이동 횟수
    
    static int[][] map;
    
    static ArrayList<Node> cloudList = new ArrayList<Node>();
    
    // ←, ↖, ↑, ↗, →, ↘, ↓, ↙
    static final int dx[] = {0 , -1, -1, -1, 0, 1, 1,  1};
    static final int dy[] = {-1, -1,  0,  1, 1, 1, 0, -1};
    
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        
        N = sc.nextInt();
        M = sc.nextInt();
        sc.nextLine();
        
        map = new int[N + 1][N + 1];
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                map[i][j] = sc.nextInt();
            }
        }
        
        InitCloud();  // 구름 초기 설정
        
        for(int i = 0 ; i < M ; i++) {
            int d = sc.nextInt(); // 이동 방향
            int s = sc.nextInt(); // 이동 칸수
            sc.nextLine();
            
            moveCloud(d, s);	// 구름 이동
            
            increaseWater();	// 물 증가
            
            copyWater();		// 물 복사
            
            createCloud();		// 구름 생성
        }
        
        System.out.println(countWater());
        
        sc.close();
    }
    
    static int countWater() { // 물 개수 카운트
        int count = 0;
        
        for(int i = 1 ; i <= N ; i++) {
          for(int j = 1 ; j <= N ; j++) {
              count += map[i][j];
          }
        }
        
        return count;
    }
    
    static void createCloud() { // 구름 생성
        ArrayList<Node> tempCloudList = new ArrayList<Node>();
        
        for(int i = 1 ; i <= N ; i++) {
            for(int j = 1 ; j <= N ; j++) {
                if(2 <= map[i][j]) {
                    
                    boolean flag = true;
                    for(int k = 0 ; k < cloudList.size() ; k++) {
                      Node n = cloudList.get(k);
                      
                      int x = n.x;
                      int y = n.y;
                      
                      if(x == i && y == j) {
                        flag = false;
                        break;
                      }
                    }
                    
                    if(flag) {
                      map[i][j] -= 2;
                      tempCloudList.add(new Node(i, j));
                    }
                    
                }
            }
        }
        
        removeCloud();
        cloudList = tempCloudList;
    }
    
    static void copyWater() { // 물 복사 마법 실행
        for(int i = 0 ; i < cloudList.size() ; i++) {
            Node n = cloudList.get(i);
            
            int x = n.x;
            int y = n.y;
            
            int count = 0;
            for(int d = 1 ; d < dx.length ; d += 2) {
                int nx = x + dx[d];
                int ny = y + dy[d];
               
                if(1 <= nx && nx <= N && 1 <= ny && ny <= N) {
                    if(0 != map[nx][ny]) {
                        count++;
                    }
                }
            }
            
            map[x][y] += count;
        }
    }
    
    static void removeCloud() {   // 구름 제거
        cloudList = new ArrayList<Node>();
    }
    
    static void increaseWater() { // 구름이 있는 칸은 비가 내려 1씩 증가
      for(int i = 0 ; i < cloudList.size() ; i++) {
          Node n = cloudList.get(i);
          
          int x = n.x;
          int y = n.y;
          
          map[x][y] += 1;
      }
    }
    
    static void moveCloud(int direction, int moveCount) {   // 구름 이동
        for(int i = 0 ; i < cloudList.size() ; i++) {
            Node n = cloudList.get(i);
          
            int x = n.x;
            int y = n.y;
          
            int nx = x + (dx[direction - 1] * moveCount);
            int ny = y + (dy[direction - 1] * moveCount);

            n = correctionCloud(new Node(nx, ny));
            
            cloudList.set(i, n);
        }
    }
    
    static Node correctionCloud(Node node) {  // 이동 후 구름이 map 범위를 벗어났을 때 구름 위치 교정
        int x = node.x;
        int y = node.y;
      
        while(!(1 <= x && x <= N)) {
            if(1 > x) {
                x += N;
            } else if(N < x){
                x -= N;
            }
        }
        
        while(!(1 <= y && y <= N)) {
            if(1 > y) {
                y += N;
            } else if(N < y){
                y -= N;
            }
        }

        return new Node(x, y);
    }
    
    static void InitCloud() { // 구름 초기 설정
        cloudList.add(new Node(N, 1));
        cloudList.add(new Node(N, 2));
        cloudList.add(new Node(N - 1, 1));
        cloudList.add(new Node(N - 1, 2));
    }
    
}

🏅 결과


🗨️ 후기

  • 문제 유형이 시뮬레이션이라서 순서대로 구현하면 되어서 쉬웠지만, 시간이 걸렸다.
  • 구현해야 할 기능을 모두 함수화하였더니 오류 발생 시 수정이 편해졌다.

📖 관련 지식

좋은 웹페이지 즐겨찾기