[백준_20057번] 마법사 상어와 토네이도_삼성 SW 역량테스트

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

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

[문제]

 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

 

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

 

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

 

 토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

 토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

 

[입력 조건]

 첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

 

[코드]

import java.util.*;

public class BaekJoon_20057 {
	static int n;
	static int[][] map;
	// 토네이도가 움직이는 순서인 서-남-동-북 순으로 모래가 퍼지는 방향 
	static int[][] dsx= {{-1,1,-2,-1,1,2,-1,1,0}, // x 이동방향
			     {-1,-1,0,0,0,0,1,1,2},  
			     {1,-1,2,1,-1,-2,1,-1,0},	
			     {1,1,0,0,0,0,-1,-1,-2}};
	static int[][] dsy= {{1,1,0,0,0,0,-1,-1,-2}, // y 이동방향
		             {-1,1,-2,-1,1,2,-1,1,0},
		             {-1,-1,0,0,0,0,1,1,2},	
		  	     {1,-1,2,1,-1,-2,1,-1,0}};
	static int[] sandpercent= {1,1,2,7,7,2,10,10,5};
	static int[] dx= {0,1,0,-1}; // 토네이도가 이동하는 서-남-동-북 순서
	static int[] dy= {-1,0,1,0};
	// 토네이도가 서-남-동-북 방향으로 이동하는 횟수, 한 턴이 끝날때마다 +2씩 증가
	static int[] dc= {1,1,2,2}; 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		
		n=sc.nextInt();
		map=new int[n][n];
		
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				map[i][j]=sc.nextInt();
		
		// 시작은 배열의 중앙
		int result=tornadoes(n/2,n/2);
		System.out.println(result);
	}
	
	static int tornadoes(int x, int y) {
		int totaloutsand=0; // 격자 밖으로 나간 모래의 양
		
		// 현재 위치
		int currentx=x;
		int currenty=y;
		
		while(true) {
			// 서-남-동-북 순으로 토네이도 이동
			for(int i=0;i<4;i++) {
				// 각 방향으로 이동하는 횟수만큼 이동 
				for(int move=0;move<dc[i];move++) {
					// 이동한 위치(예시에서의 y의미)
					int nx=currentx+dx[i];
					int ny=currenty+dy[i];
					
					/*
					 * 토네이도가 범위를 벗어나는 경우는 소멸한 경우
					 * 이때는 격자 밖으로 나간 모래의 양 return 
					 */
					if(nx<0||ny<0||nx>=n||ny>=n) 
						return totaloutsand;
					
					//////////////예시에서의 y칸////////////// 
					int sand=map[nx][ny]; // y에 있는 모래의 양
					map[nx][ny]=0; // y에 있는 모든 모래 이동하기 때문에 0으로 초기화
					int spreadtotal=0; 
					
					// 해당 방향에서 비율이 적혀있는 칸으로 해당 비율만큼 모래 이동
					for(int j=0;j<9;j++) {
						/*
						 * i는 서-남-동-북 중 해당하는 방향 의미
						 * j는 y를 기준으로 설정한 각 비율이 있는 위치를 의미
						 */
						int sandx=nx+dsx[i][j];
						int sandy=ny+dsy[i][j];
						// y에 있었던 모래에서 각 칸에 적혀있는 비율만큼 이동 
						int spread=(sand*sandpercent[j])/100;
						
						// 범위를 넘어가면 격자 밖으로 나간 모래이기 때문에 누적
						if(sandx<0||sandy<0||sandx>=n||sandy>=n)
							totaloutsand+=spread;
						// 범위를 넘어가지 않았다면 비율 칸에 모래 누적
						else
							map[sandx][sandy]+=spread;
						
						spreadtotal+=spread; // y에 있던 모래중 이동한 모래의 양 구하기 -> 나머지 α 칸으로 이동
					}
					
					//////////////예시에서의 α칸////////////// 
					// α은 y에서 서-남-동-북 중 해당하는 방향으로 한 칸 이동한 곳
					int alphax=nx+dx[i];
					int alphay=ny+dy[i];
					// α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양
					int alpha=sand-spreadtotal;
					
					// 범위를 넘어가면 격자 밖으로 나간 모래이기 때문에 누적
					if(alphax<0||alphay<0||alphax>=n||alphay>=n) 
						totaloutsand+=alpha;
					// 범위를 넘어가지 않았다면 α 칸에 모래 누적
					else
						map[alphax][alphay]+=alpha;
					
					
					// 현재 위치 갱신
					currentx=nx;
					currenty=ny;
				}
			}
			
			// 토네이도가 이동하는 횟수는 한 턴이 끝날때마다 +2씩 증가
			for(int k=0;k<4;k++)
				dc[k]+=2;
		}
	}

}

 

[고찰]

 이번 문제는 사실 이전에 풀어보려 시도했지만 해설을 봐도 토네이도가 이동하는 방향에 따라 비율이 적혀있는 dsx와 dsy 배열이 왜 저렇게 만들어지는지 이해가 가지 않아 포기했었던 문제였다. 얼마전부터 시작한 코딩 스터디에서 해당 문제를 다시 풀어야하는 기회를 얻어 이번에는 해결해보고자 하는 마음으로 문제 이해부터 다시 차근차근 시도해보았다. 비록 다른 사람의 풀이와 코드를 참고해 정답처리를 받았지만 쉽게 포기하지 않은 것에 의의를 두고 여러번 복습해보면서 내것으로 만들어야겠다고 다짐했다. 

 

[참고한 블로그]

https://alwaysbemoon.tistory.com/225

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

 

[문제해결 정리]

 위에 잘 정리된 블로그가 있지만 나름대로 문제 해결 아이디어를 정리해보고자 한다. 우선 문제의 큰 틀은 "x 위치에서 y로 이동 -> 비율이 적혀있는 칸과 α 칸에 y에 있던 모래 뿌리기 -> 현재위치 갱신" 이다. 큰 틀은 잡았으니 각 단계에서 필요한 과정을 코드로 구현하면 된다. 

 

*** 1) 토네이도 이동 방향

 토네이도의 이동 방향은 위 사진과 같다. 이동 방향의 순서는 서-남-동-북 순으로 진행되고 이동하는 칸의 갯수는 (1,1,2,2) -> (3,3,4,4) -> (5,5,6,6) 으로 변하는 것을 확인할 수 있다. 즉 한 턴이 끝나면 각 방향의 이동 횟수는 +2만큼 증가하는 규칙을 갖는다. 

 

*** 2) 비율이 적혀있는 칸으로 모래 뿌리기

 비율에 적혀있는 칸으로 뿌려지는 모래는 y에 있는 모래에서 각 칸에 적혀있는 비율만큼이다. 이를 위해서는 토네이도의 이동방향인 서-남-동-북 각 방향에에 모래의 확산 방향을 알아야한다. 이를 저장한 것이 바로 dsx와 dsy 배열이다. 각 행은 서-남-동-북 순으로 방향을 의미하고, 열은 y를 기준으로 봤을때 아래 빨간 색으로 적혀진 순서대로의 배열의 위치를 나타낸다. 아래 표는 서쪽으로 토네이도가 이동한 경우를 나타낸 것이다. 

 

		2% ③
	10% ⑦	7% ④	1% ①
5% ⑨	α	y	← x
	10% ⑧	7% ⑤	1% ②
		2% ⑥

 

토네이도가 남쪽으로 이동하는 경우는 아래 표와 같다.

 

	1% ①	x ↓	1% ②
2% ③	7% ④	y	7% ⑤	2% ⑥
	10% ⑦	α	10% ⑧
		5% ⑨

 

즉, 각 방향으로 초기의 격자판을 돌려 y를 기준으로 각 비율이 적혀진 배열로 이동할 때의 이동 방향을 적어준 것이 dsx와 dsy 배열이다.

 

 dsx와 dsy 배열까지 만들었으면 그 뒤는 쉽다. y에 있는 모래에서 각 비율에 적혀진 만큼 모래를 이동시키면 된다. 이때 격자판을 초과한 경우는 결과 값에 누적시키고 그렇지 않은 경우에는 비율 칸에 모래를 누적시키면 된다. 

 

*** 3) α칸으로 모래 뿌리기

 α 칸은 서-남-동-북 중 해당하는 방향을 한 칸 이동한 곳을 말한다. 이러한 α 칸으로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양이기 때문에 (y칸에 있던 모래 양 - 비율 칸으로 이동하는 모래의 총합)이  α 칸으로 이동하는 모래의 양이 된다. 여기까지의 모든 과정이 끝나면 현재 위치를 갱신해준다.