[삼성 SW 역량 테스트 기출 문제] 마법사 상어와 비바라기 - 레벨1

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

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

 

일단 이 문제에서 가장 어려웠던점은 -1행이 되면 마지막행으로 변하고 마지막행 + 1 이 되면 0행으로 변하는 그런 과정을 생각하는 것이 가장 어려웠습니다.

사실 맨 아래의 실패코드를 통해서 보면 while문을 통해서 구현할 수 있었는데 그렇게할시 시간초과로 인하여 문제가 풀리지 않습니다. 

그렇기 떄문에 아래의 코드에서 위의 과정을 쉽게 풀수 있는 연산식을 구해야만 합니다.

 

cloudxvar = (originxvar + N + (dx[d]*s)%N) %N;
cloudyvar = (originyvar + N + (dy[d]*s)%N) %N;

 

이 연산식인데 이걸 아무리 구할려고해도 거의 다 구하다가 못구했습니다..

이 연산식의 장점은 -1행이든 N+1 행이든 같은 식으로 구현하여 편하게 구할 수 있다는 것입니다.

자주 나올 공식이니 반드시 외우고 이해해야할 것 같습니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N,M;
	static int[][] map;
	
	static Queue<Integer> cloudx = new LinkedList<Integer>();
	static Queue<Integer> cloudy = new LinkedList<Integer>();
	
	//서쪽, 북서쪽, 북쪽, 북동쪽, 동쪽 (반시계방향으로..)
	static int[] dx = {0,-1,-1,-1,0,1,1,1};
	static int[] dy = {-1,-1,0,1,1,1,0,-1};
	
	public static void main(String[] args) throws IOException {
		

		
		//Scanner sc = new Scanner(System.in);
		
//		N=sc.nextInt(); M=sc.nextInt();		
//		cloudx = new int[]{N-1, N-1, N-2, N-2};
//		cloudy = new int[]{0, 1, 0, 1};
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		
		cloudx.add(N-1);
		cloudx.add(N-1);
		cloudx.add(N-2);
		cloudx.add(N-2);
		
		cloudy.add(0);
		cloudy.add(1);
		cloudy.add(0);
		cloudy.add(1);
		
		map = new int[N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				
			}
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int d = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			
			rainsimulate(d-1, s);
		}
    	
		int sumresult = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				sumresult += map[i][j];
			}
		}
		
		System.out.println(sumresult);
		
	}
	
	public static void rainsimulate(int d, int s) {
		ArrayList<Integer> temparrx = new ArrayList<Integer>();
		ArrayList<Integer> temparry = new ArrayList<Integer>();
		
		
		//queue poll 을 하면 queue 사이즈가 줄어든다느 것을 잊지말자.
		int cloudxqueuesize = cloudx.size();
		
		for(int i=0;i<cloudxqueuesize;i++) {
			//System.out.println("why it works only "+i);
			//System.out.println(cloudx.size());
			int cloudxvar = cloudx.poll();
			int cloudyvar = cloudy.poll();
			
			int originxvar = cloudxvar;
			int originyvar = cloudyvar;
			
			int distancex = dx[d]*s;
//			while(distancex != 0) {
//				if(distancex > 0) {
//					cloudxvar += 1;
//					if(cloudxvar > N-1) {
//						cloudxvar = 0;
//					}
//					distancex -= 1;
//				}
//				else if(distancex < 0) {
//					cloudxvar -= 1;
//					if(cloudxvar < 0) {
//						cloudxvar = N - 1;
//					}
//					distancex += 1;
//				}
//			}
//			
//			int distancey = dy[d]*s;
//			while(distancey != 0) {
//				if(distancey > 0) {
//					cloudyvar += 1;
//					if(cloudyvar > N-1) {
//						cloudyvar = 0;
//					}
//					distancey -= 1;
//				}
//				else if(distancey < 0) {
//					cloudyvar -= 1;
//					if(cloudyvar < 0) {
//						cloudyvar = N - 1;
//					}
//					distancey += 1;
//				}
//			}
			

			
			
			
//			if(cloudxvar > N-1 ) {
//				cloudxvar = cloudxvar % N;
//			}
//			if(cloudyvar > N-1) {
//				cloudyvar = cloudyvar % N;
//			}
//			if(cloudxvar < 0 ) {
//				System.out.println("cloudvar % N : "+cloudxvar%N);
//				
//				cloudxvar = Math.abs((originxvar + (dx[d]*s) % N))%N;
//			}
//			if(cloudyvar < 0) {
//				cloudyvar = (originyvar + (dx[d]*s) %N)%N;
//			}
			//System.out.println("cloudxvar :" + cloudxvar + "cloudyvar:"+cloudyvar);
			
			cloudxvar = (originxvar + N + (dx[d]*s)%N) %N;
			cloudyvar = (originyvar + N + (dy[d]*s)%N) %N;
			temparrx.add(cloudxvar);
			temparry.add(cloudyvar);
		}
		
		
		
		for(int i=0;i<temparrx.size();i++) {
			
			map[temparrx.get(i)][temparry.get(i)] += 1;
		}
		
		for(int i=0;i<temparrx.size();i++) {
			int cloudxvar = temparrx.get(i);
			int cloudyvar = temparry.get(i);
			for(int j=1;j<8;j+=1) {
				if(j%2==0) {
					continue;
				}
				if(cloudxvar + dx[j] >= 0 && cloudxvar + dx[j] <= N-1 && cloudyvar + dy[j] >= 0 && cloudyvar + dy[j] <= N-1){
					if(map[cloudxvar + dx[j]][cloudyvar+dy[j]] >= 1) {
						
						map[cloudxvar][cloudyvar] += 1;
					}
				} 

			}		
		}		
		
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				boolean sameflag = false;
				if(map[i][j] >= 2) {
					
					int newcloudx = i;
					int newcloudy = j;					
					for(int k=0;k<temparrx.size();k++) {
						int cloudxvar = temparrx.get(k);
						int cloudyvar = temparry.get(k);
						if(cloudxvar == newcloudx && cloudyvar == newcloudy) {
							sameflag = true;
							continue;
						}
					}
					
					if(!sameflag) {
						map[i][j] -= 2;	
						cloudx.add(newcloudx);
						cloudy.add(newcloudy);						
					}
				}
			}
		}
		

		
		
		
	}
	
	

}

BufferedReader를 사용하면 852 ms 가 나오면서 겨우 통과

 

 

 

 

문제는 다 풀었는데 문제는 시간초과가 발생한다..

 

package Main;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N,M;
	static int[][] map;
	
	static Queue<Integer> cloudx = new LinkedList<Integer>();
	static Queue<Integer> cloudy = new LinkedList<Integer>();
	
	//서쪽, 북서쪽, 북쪽, 북동쪽, 동쪽 (반시계방향으로..)
	static int[] dx = {0,-1,-1,-1,0,1,1,1};
	static 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();		
//		cloudx = new int[]{N-1, N-1, N-2, N-2};
//		cloudy = new int[]{0, 1, 0, 1};
		
		
		
		cloudx.add(N-1);
		cloudx.add(N-1);
		cloudx.add(N-2);
		cloudx.add(N-2);
		
		cloudy.add(0);
		cloudy.add(1);
		cloudy.add(0);
		cloudy.add(1);
		
		map = new int[N][N];
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		for(int i=0;i<M;i++) {
			int d = sc.nextInt();
			int s = sc.nextInt();
			
			rainsimulate(d-1, s);
		}
    	
		int sumresult = 0;
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				sumresult += map[i][j];
			}
		}
		
		System.out.println(sumresult);
	}
	
	public static void rainsimulate(int d, int s) {
		ArrayList<Integer> temparrx = new ArrayList<Integer>();
		ArrayList<Integer> temparry = new ArrayList<Integer>();
		
		
		//queue poll 을 하면 queue 사이즈가 줄어든다느 것을 잊지말자.
		int cloudxqueuesize = cloudx.size();
		
		for(int i=0;i<cloudxqueuesize;i++) {
			//System.out.println("why it works only "+i);
			//System.out.println(cloudx.size());
			int cloudxvar = cloudx.poll();
			int cloudyvar = cloudy.poll();
			
			int originxvar = cloudxvar;
			int originyvar = cloudyvar;
			
			int distancex = dx[d]*s;
			while(distancex != 0) {
				if(distancex > 0) {
					cloudxvar += 1;
					if(cloudxvar > N-1) {
						cloudxvar = 0;
					}
					distancex -= 1;
				}
				else if(distancex < 0) {
					cloudxvar -= 1;
					if(cloudxvar < 0) {
						cloudxvar = N - 1;
					}
					distancex += 1;
				}
			}
			
			int distancey = dy[d]*s;
			while(distancey != 0) {
				if(distancey > 0) {
					cloudyvar += 1;
					if(cloudyvar > N-1) {
						cloudyvar = 0;
					}
					distancey -= 1;
				}
				else if(distancey < 0) {
					cloudyvar -= 1;
					if(cloudyvar < 0) {
						cloudyvar = N - 1;
					}
					distancey += 1;
				}
			}
			

			
			
			
//			if(cloudxvar > N-1 ) {
//				cloudxvar = cloudxvar % N;
//			}
//			if(cloudyvar > N-1) {
//				cloudyvar = cloudyvar % N;
//			}
//			if(cloudxvar < 0 ) {
//				System.out.println("cloudvar % N : "+cloudxvar%N);
//				
//				cloudxvar = Math.abs((originxvar + (dx[d]*s) % N))%N;
//			}
//			if(cloudyvar < 0) {
//				cloudyvar = (originyvar + (dx[d]*s) %N)%N;
//			}
			//System.out.println("cloudxvar :" + cloudxvar + "cloudyvar:"+cloudyvar);
			temparrx.add(cloudxvar);
			temparry.add(cloudyvar);
		}
		
		
		
		for(int i=0;i<temparrx.size();i++) {
			
			map[temparrx.get(i)][temparry.get(i)] += 1;
		}
		
		for(int i=0;i<temparrx.size();i++) {
			int cloudxvar = temparrx.get(i);
			int cloudyvar = temparry.get(i);
			for(int j=1;j<8;j+=1) {
				if(j%2==0) {
					continue;
				}
				if(cloudxvar + dx[j] >= 0 && cloudxvar + dx[j] <= N-1 && cloudyvar + dy[j] >= 0 && cloudyvar + dy[j] <= N-1){
					if(map[cloudxvar + dx[j]][cloudyvar+dy[j]] >= 1) {
						
						map[cloudxvar][cloudyvar] += 1;
					}
				} 

			}		
		}		
		
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				boolean sameflag = false;
				if(map[i][j] >= 2) {
					
					int newcloudx = i;
					int newcloudy = j;					
					for(int k=0;k<temparrx.size();k++) {
						int cloudxvar = temparrx.get(k);
						int cloudyvar = temparry.get(k);
						if(cloudxvar == newcloudx && cloudyvar == newcloudy) {
							sameflag = true;
							continue;
						}
					}
					
					if(!sameflag) {
						map[i][j] -= 2;	
						cloudx.add(newcloudx);
						cloudy.add(newcloudy);						
					}
				}
			}
		}
		

		
		
		
	}
	
	

}