[백준_21610번 ] 마법사 상어와 비바라기_삼성 SW 역량테스트

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

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

[문제]

 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.

 

 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.

 

 비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.

 

1. 모든 구름이 di 방향으로 si칸 이동한다.
2. 각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
3. 구름이 모두 사라진다.
4. 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
   • 이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
   • 예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
5. 바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.

 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.

 

[입력 조건]

• 첫째 줄에 N, M이 주어진다.
• 둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.
• 다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.

 

[코드]

import java.util.*;

class Point_21610 {
	int x,y;
	
	public Point_21610(int x, int y) {
		this.x=x;
		this.y=y;
	}
}

public class BaekJoon_21610 {
	static int n,m;
	static int[][] map;
	static boolean[][] check;
	static ArrayList<Point_21610> cloud=new ArrayList<>(); // 구름 위치 저장
	static int[][] move= {{0,0},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1}};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		map=new int[n+1][n+1];
		check=new boolean[n+1][n+1];
		
		// 초기 구름의 위치 삽입
		cloud.add(new Point_21610(n,1));
		cloud.add(new Point_21610(n,2));
		cloud.add(new Point_21610(n-1,1));
		cloud.add(new Point_21610(n-1,2));

		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				map[i][j]=sc.nextInt();

		for(int i=0;i<m;i++) {
			int d=sc.nextInt();
			int s=sc.nextInt();
			
			// d방향으로 s칸 만큼 모든 구름 이동
			for(int j=0;j<s;j++) {
				for(int k=0;k<cloud.size();k++) {
					Point_21610 p=cloud.get(k);
					int nx=p.x+move[d][0];
					int ny=p.y+move[d][1];
					
					// 이동 좌표가 배열 밖으로 넘어간 경우는 인덱스 조정
					if(!(nx<=n&&ny<=n&&nx>=1&&ny>=1)) {
						/*
						 * x 좌표가 왼쪽으로 넘어간 경우는 오른쪽 끝 값으로 변경
						 * 오른쪽으로 넘거간 경우는 왼쪽 끝 값으로 변경
						 * 
						 * y 좌표가 위쪽으로 넘어간 경우는 맨 아랫 값으로 변경
						 * 아랫쪽으로 넘어간 경우는 맨 위 값으로 변경
						 * 
						 * 이때 배열 인덱스는 1~n 이라는 것 주의!
						 */
						if(nx==0) nx=n;
						else if(nx==n+1) nx=1;
						
						if(ny==0) ny=n;
						else if(ny==n+1) ny=1;
					}
					
					// 이동한 구름 좌표로 갱신
					cloud.set(k,new Point_21610(nx,ny));
				}
			}
			
			// 구름이 있는 곳에 비 뿌리기(배열 값 1 증가)
			for(int j=0;j<cloud.size();j++) {
				Point_21610 p=cloud.get(j);
				map[p.x][p.y]+=1;
				
				check[p.x][p.y]=true; // 비가 있던 곳 체크
			}
			
			// 대각선에 물이 있는 칸 개수 count
			for(int j=0;j<cloud.size();j++) {
				Point_21610 p=cloud.get(j);
				int count=0;
			
				// move 배열에서 인덱스가 2,4,6,8이 대각선 방향
				for(int k=2;k<=8;k+=2) {
					int nx=p.x+move[k][0];
					int ny=p.y+move[k][1];
					
					/*
					 * 물복사버그 마법은 범위를 벗어난 곳은 count 하지 않기 때문에
					 * 배열 인덱스 조정 과정이 필요 없다.  
					 */
					if(nx<=n&&ny<=n&&nx>=1&&ny>=1) 
						if(map[nx][ny]!=0)
							count++;
				}
				
				map[p.x][p.y]+=count;
			}
			
			cloud.clear(); // 구름 소멸
			
			/*
			 * 구름이 있었던 칸을 제외한 나머지 칸 중 비의 양이 2 이상인 칸들은
			 * 구름 생성 후 물의 양 2 감소 
			 */
			for(int x=1;x<=n;x++) {
				for(int y=1;y<=n;y++) {
					// 이전에 비가 있던 자리는 넘어간다.
					if(check[x][y])
						continue;
					
					// 구름 생성
					if(map[x][y]>=2) {
						map[x][y]-=2;
						cloud.add(new Point_21610(x,y));
					}
				}
			}
			
			// 다음 경우를 위해 구름이 있던 자리 체크하는 배열 초기화
			check=new boolean[n+1][n+1];
		}
		
		// 물의 양 합 구하기
		int result=0;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				result+=map[i][j];
		
		System.out.println(result);
	}
}

 

[고찰] 

 이번 문제는 주어진 조건을 모두 구현해야 하는 시뮬레이션 문제였다. 문제가 길다보니 우선 문제를 이해하고 구조화 하여 구현해야 하는 조건들을 간결화 하였다. 이번 문제는 특히 문제의 흐름이 복잡하다 보니 따로 함수로 구현하지 않고 문제의 흐름이 보이게끔 메인 함수 내에 모든 과정을 구현하였다. 그리고 문제를 풀기전 아래와 같이 어떤 과정을 구현해야 하는지 문제의 흐름을 적어보면서 이해하였다. 

 

처음 구름 생성(지정된 (n,1), (n,2), (n-1,1), (n-1,2) 좌표를 연결리스트에 저장) -> m번 입력받은 d 방향으로 s칸 만큼 이동 -> 구름이 있는 칸에 비를 뿌림(배열 값을 1 증가) -> 방금 증가한 배열 칸을 중심으로 4개의 대각선 방향의 비가 있는 칸의 개수만큼 배열 값 증가(물복사 버그 마법) -> 구름 소멸 -> 구름이 존재했던 칸을 제외하고, 비의 양이 2 이상 있던 칸에 구름 생성 

 

위 과정이 이번 문제의 흐름을 나름대로 정리해 본 것이다. 여기서 주의할 점은 배열이 위,아래, 양 옆이 연결되어 있다고 가정하기 때문에 인덱스가 배열 값을 넘어갈 경우는 조정해주는 과정이 필요하다는 것이다. 하지만 대각선에 비가 있는 칸의 개수를 count 할 경우는 배열이 이어져있다고 생각하지 않기 때문에 주의해야 한다. 또한 모든 과정이 끝난 후에는 다음 경우를 위해 비가 있는 자리를 체크하는 boolean 배열은 초기화해주는 것을 잊으면 안된다.