[백준] 20057번 : 마법사 상어와 토네이도 - 자바[Java]

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

20057번: 마법사 상어와 토네이도

풀이

토네이도는 좌향부터 시작해서 좌, 하, 우, 상 순서대로 방향을 바꾸고, 1칸, 1칸, 2칸, 2칸... n-2칸, n-2칸, n-1칸, n-1칸, n-1칸을 이동한다. 즉, 각 칸 수마다 2번 이동하고 마지막 n-1칸을 이동할 때는 3번 이동한다.

 

토네이도가 이동할 때마다 모래가 이동하는 위치와 비율을 3차원 배열을 통해 저장한다.

	// 방향: 좌, 하, 우, 상
	static int[] dx = {0, 1, 0, -1}; // 행
	static int[] dy = {-1, 0, 1, 0}; // 열
	
	static int[][][] dustDir = { // 각각 토네이도가 새로 이동한 위치를 중심으로 행, 열 위치, 모래가 이동하는 비율
			{ {-2, 0, 2}, {-1,-1,10}, {-1,0,7}, {-1, 1, 1}, {0, -2, 5}, {1,-1,10}, {1,0,7}, {1,1,1}, {2,0,2} },
			{ {0, -2, 2}, {-1,-1,1}, {0,-1,7}, {1, -1, 10}, {2, 0, 5}, {-1,1,1}, {0,1,7}, {1,1,10}, {0,2,2} },
			{ {-2, 0, 2}, {-1,-1,1}, {-1,0,7}, {-1, 1, 10}, {0, 2, 5}, {1,-1,1}, {1,0,7}, {1,1,10}, {2,0,2} },
			{ {0, -2, 2}, {1,-1,1}, {0,-1,7}, {-1, -1, 10}, {-2, 0, 5}, {-1,1,10}, {0,1,7}, {1,1,1}, {0,2,2} }
	};

 

수도코드

tx = n/2 // 토네이도 행 위치
ty = n/2 // 토네이도 열 위치
line = 0 // 한 번에 토네이도가 이동하는 칸 수
cnt = 0 // 토네이도가 line 칸 수만큼 이동한 횟수
dir = -1 // 토네이도가 이동하는 방향 인덱스

while () {
    dir++
    cnt++
    if (tx == 0 && ty == 0) break
    if (line < n-1 && cnt >= 3) {
    	cnt = 1
        line++
    }
    
    for (line) {
    	tx += dx[dir]
        ty += dy[dir]
        
        if (map[tx][ty] > 0) {
            int sum = 0
            for (9번) {
            	sum += dust
                if (모래가 이동한 곳이 격자 안이라면) map[][] += dust
                else answer += dust
            }
            
            if (남은 모래가 이동한 곳이 격자 안이라면)
            	map[][] = map[tx][ty] - sum
            else answer += map[tx][ty] - sum
            map[tx][ty] = 0
        }
    }
}

 

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int n;
	static int[][] map;
	
	// 방향: 좌, 하, 우, 상
	static int[] dx = {0, 1, 0, -1}; // 행
	static int[] dy = {-1, 0, 1, 0}; // 열
	
	// 각각 토네이도가 새로 이동한 위치를 중심으로 행, 열 위치, 모래가 이동하는 비율
	static int[][][] dustDir = {
			{ {-2, 0, 2}, {-1,-1,10}, {-1,0,7}, {-1, 1, 1}, {0, -2, 5}, {1,-1,10}, {1,0,7}, {1,1,1}, {2,0,2} },
			{ {0, -2, 2}, {-1,-1,1}, {0,-1,7}, {1, -1, 10}, {2, 0, 5}, {-1,1,1}, {0,1,7}, {1,1,10}, {0,2,2} },
			{ {-2, 0, 2}, {-1,-1,1}, {-1,0,7}, {-1, 1, 10}, {0, 2, 5}, {1,-1,1}, {1,0,7}, {1,1,10}, {2,0,2} },
			{ {0, -2, 2}, {1,-1,1}, {0,-1,7}, {-1, -1, 10}, {-2, 0, 5}, {-1,1,10}, {0,1,7}, {1,1,1}, {0,2,2} }
	};

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	n = Integer.parseInt(br.readLine());
    	
    	map = new int[n][n];
    	
    	for (int i = 0; i < n; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		for (int j = 0; j < n; j++) {
    			map[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
    	
    	int tx = n / 2; // 토네이도 행 위치
    	int ty = n / 2; // 토네이도 열 위치
    	
    	int cnt = 0; // 토네이도가 line 칸 수만큼 이동한 횟수
    	int dir = -1; // 토네이도 방향 인덱스
    	int line = 1; // 한 번에 토네이도가 이동하는 칸 수
    	
    	int outDustSum = 0;
    	while (true) {
    		dir = (dir+1) % 4;
    		cnt++;
    		if (tx == 0 && ty == 0) {
    			break;
    		}
    		else if (line < n-1 && cnt >= 3) {
    			cnt = 1;
    			line++;
    		}
    		
    		for (int k = 0; k < line; k++) {
    			tx += dx[dir];
    			ty += dy[dir];
    			
    			if (map[tx][ty] <= 0) continue;
    			
    			int dustSum = 0;
    			
    			for (int i = 0; i < 9; i++) {
    				int dust = (int)(map[tx][ty] * ((double)dustDir[dir][i][2] / 100));
    				dustSum += dust;
    				
    				int nx = tx + dustDir[dir][i][0];
    				int ny = ty + dustDir[dir][i][1];
    				if (nx >= 0 && nx < n && ny >= 0 && ny < n) { // 격자 안인 경우
    					map[nx][ny] += dust;
    				}
    				else { // 격자 밖으로 나간 경우
    					outDustSum += dust;
    				}
    			}
    			
    			// 남은 모래
    			int nx = tx + dx[dir];
				int ny = ty + dy[dir];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n) { // 격자 안인 경우
					map[nx][ny] += map[tx][ty] - dustSum;
				}
				else { // 격자 밖으로 나간 경우
					outDustSum += map[tx][ty] - dustSum;
				}
				
				map[tx][ty] = 0;
    		}
    	}
    	
    	System.out.println(outDustSum);
    }
}

 

다른 풀이

https://alwaysbemoon.tistory.com/225

[백준 20057, Java] 마법사 상어와 토네이도

https://www.acmicpc.net/source/67824655