우매함의 봉우리를 넘어서며 개발하면서 기록하기

백준 20057. 마법사 상어와 토네이도 (상어 시리즈)

04 May 2021

문제 바로가기

마법사 상어와 토네이도

문제 요약

파이어볼을 배운 마법사 상어는 이번에는 토네이도를 배워서 연습을 한다고 한다. N×N 격자로 이루어진 모래밭에서 연습을 하며 시전을 하게 되면 격자의 가운데 칸부터 토네이도가 돌면서 바깥으로 이동을 한다. 토네이도 이동

토네이도가 한칸 이동할 때마다 아래 그림과 같이 일정한 비율료 모래가 흩날린다. 모래가 날라다녀요!

a는 y에 있는 모래가 % 비율로 적혀있는 만큼 모두 이동을 하게되고 남은 모래가 이동하게 된다. 또한, % 비율로 이동되는 모래의 양은 항상 소수점 아래를 버림한다.

위의 그림은 토네이도가 왼쪽으로 이동할때며, 다른 방향으로 이동하게 되면 위 그림을 회전시켜 확인하면 된다.

토네이도는 (1,1)을 지나고 소멸되며, 모래가 격자 바깥으로 나간 양을 구하는 문제이다.

문제 풀이 포인트

먼저, N×N 격자 바깥으로 나간 모래의 양을 구하는 것이기 때문에, N×N에서 양쪽으로 2칸씩 추가한 (N+4)×(N+4)의 격자를 만들어 따로 경계 체크를 하지 않고 토네이도가 바깥까지 나갈때까지 그냥 돌리게 하였다.

또한, 토네이도가 이동하는 것을 보면 왼쪽(←), 아래(↓), 오른쪽(→), 위(↑) 순서대로 1칸 2번, 2칸 2번, 3칸 2번씩 늘어나는 것을 알 수 있다. 즉, 같은 칸 수를 2회씩 이동하는 것이다. 이부분을 확인하여 반복문을 추가한다면 더 쉽게 체크할 수 있다.

토네이도의 모래를 옮기는 작업은 규칙성은 찾았으나 반복문으로 구현하니 시간초과가 자꾸 나서 하드코딩식으로 만들었다.

문제 코드[JAVA]

코드 펼치기 

import java.util.*;

public class Main {
  static int N, ans;
  static int[][] map;
  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    map = new int[N+4][N+4]; // 경계 바깥 2칸씩 추가로 생성
    for(int i = 2; i < N+2; i++) { // 바깥 2칸을 제외하고 초기화 
      for(int j = 2; j < N+2; j++) {
        map[i][j] = sc.nextInt();
      }
    }
    solve();
    System.out.println(ans);
    sc.close();
  }
  private static void solve() {
    int d = 2;
    int[] t = new int[] {(N+4)/2, (N+4)/2, 0}; // 시작 위치 및 가는 방향
    L:while(true) { 
      for(int k = 0; k < d/2; k++) { // 이동하는 칸의 크기가 2 단위로 늘어나는 것을 구현
        if(t[0] == 2 && t[1]== 2) break L; // 만약 마지막 지점에 도착했다면 중단
         t[0] += dx[t[2]]; 
         t[1] += dy[t[2]];
         //System.out.println((t[0]-2) + ":" + (t[1]-2));
         
         wind(t[0], t[1], t[2]); // 이동하는 위치 및 방향 
      }
      if(++t[2] > 3) t[2] = 0;
      
      d++;
    }
    //print();
        // 바깥쪽에 있는 모래의 양 계산
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j < N+4; j++) {
        ans += map[j][i];
        ans += map[j][i+N+2];
      }
    }
    for(int i = 0; i < 2; i++) {
      for(int j = 2; j < N+2; j++) {
        ans += map[i][j];
        ans += map[i+N+2][j];
      }
    }
    
  }
  private static void print() {
    for(int i = 0; i < map.length; i++) {
      for(int j = 0; j < map[i].length; j++) {
        System.out.print(map[i][j] + " ");
      }
      System.out.println();
    }
    
  }
  private static void wind(int x, int y, int d) {
    // 토네이도가 가야하는 위치(x,y) -> (x,y)에 있는 모래를 옮기자.
    // 이때 토네이도의 이동방향은 d
    int sand = map[x][y];
    map[x][y] = 0;
    int a1 = (int) (sand * 0.01);
    int a2 = (int) (sand * 0.02);
    int a5 = (int) (sand * 0.05);
    int a7 = (int) (sand * 0.07);
    int a10 = (int) (sand * 0.1);
    int a = sand - (2*a1 + 2*a2 + a5 + 2*a7 + 2*a10);
    
    // 윗방향
    int up = d - 1;
    if(up < 0) up = 3;
    //아래방향
    int down = d + 1;
    if(down > 3) down = 0;
    
    // 첫번째줄
    map[x + (dx[up] * 2)][y + (dy[up] * 2)] += a2;
    
    //두번째 줄		
    map[x + dx[up] - dx[d]][y + dy[up] - dy[d]] += a1;
    map[x + dx[up]][y + dy[up]] += a7;
    map[x + dx[up] + dx[d]][y + dy[up] + dy[d]] += a10;
    
    // 세번째 줄
    map[x + dx[d]][y + dy[d]] += a;
    map[x + (dx[d] * 2)][y + (dy[d] * 2)] += a5; 
    
    // 네번째 줄
    map[x + dx[down] - dx[d]][y + dy[down] - dy[d]] += a1;
    map[x + dx[down]][y + dy[down]] += a7;
    map[x + dx[down] + dx[d]][y + dy[down] + dy[d]] += a10;

    // 다섯번째 줄
    map[x + (dx[down] * 2)][y + (dy[down] * 2)] += a2;
  }

  static int[] dx = {0, 1, 0, -1}; // 왼 아 오 위
  static int[] dy = {-1, 0, 1, 0};
}

Related posts