[백준] 21610번_마법사 상어와 비바라기 (구현_JAVA)

구현 문제는 시간초과가 나오기 힘들다는데

엄청난 반복문으로 시간초과가 발생했다.

 

반복문을 사용하지 않아도 되는데,

당연하게 반복문을 사용해서 시간초과가 발생한 것이다.

 

근데 어디가 문제인지 몰라 결국 검색했다.

아쉬워 나 스스로 맞힐 수 있었는데..!

 

 

---

문제

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

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

 

 

---

설계

알고리즘[접근방법] : 구현

딱히 노하우가 없다. 구현은 구현일 뿐...

 

1. 가장 먼저 배열 값을 2차원 배열 map 저장한다. > 배열이 1부터 시작하니까 범위를 n+1로 한다.

2. 탐색 배열을 마든다.

3. 최초 구름 좌표를 list인 cloud에 저장한다.

4. 입력받은 d방향으로 s칸 이동한다 > 기존 좌표 값에 r배열에 방향값을 넣고 s를 곱한다.

5. 범위에서 벗어났을 때 좌표 값이 n보다 크면 계속 -n을 하고, 좌표 값이 0보다 작다면 계속 +n을 한다.

6. isvisited배열에서 현재 구름 좌표값을 true로 변경하고, 현재 구름 좌표의 값을 +1 한다.

7. 대각선을 탐색하고 물이 있는 좌표의 개수만큼 +1을 해준다

8. 물의 양이 2 이상이면 물이 2 감소하는데, isvisited배열의 값이 true이면 제외한다.

 

 

---

코드

 

import java.util.*;
import java.util.Scanner;

public class Test_21610_마법사상어와비바라기 {	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//배열 크기
		int n = sc.nextInt();
		
		//이동 횟수
		int m = sc.nextInt();
	
		//2차원 배열 생성 및 값 입력받기
		int[][] map = new int[n+1][n+1];
		for(int i=1; i<n+1; i++) {
			for(int j=1; j<n+1; j++) {
				map[i][j]=sc.nextInt();
			}
		}

		//탐색 배열
		int[] r = {0, -1, -1, -1, 0, 1, 1, 1};
		int[] c = {-1, -1, 0, 1, 1, 1, 0, -1};

		
		//구름 생성 초기화
		List<Integer> cloud = new ArrayList();
		cloud.add(n);	cloud.add(1);
		cloud.add(n);	cloud.add(2);
		cloud.add(n-1);	cloud.add(1);
		cloud.add(n-1);	cloud.add(2);
        
		
		for(int i=0; i<m; i++) {
			int d = sc.nextInt()-1;	//방향
			int s = sc.nextInt();	//거리

			//1. d방향으로 s칸 이동한다
			for(int p=0; p<cloud.size(); p+=2) {	
				//list이름.set(인덱스, 값)
				cloud.set(p, cloud.get(p)+(r[d]*s));		//r
				cloud.set(p+1, cloud.get(p+1)+(c[d]*s));	//c		
			}

			//범위 넘어가는 것 조정
			for(int k=0; k<cloud.size(); k++) {
				while(cloud.get(k)<=0) { cloud.set(k, cloud.get(k)+n);}
				while(n<cloud.get(k)) { cloud.set(k, cloud.get(k)-n);}
			}
			
			//구름 좌표 확인 배열
			boolean[][] isvisited = new boolean[n+1][n+1];
			for(int k=0; k<cloud.size(); k+=2) {
				isvisited[cloud.get(k)][cloud.get(k+1)]=true;
			}
			
					
			//2. 구름이 있는 칸의 바구니에 저장된 물이 1 증가한다.
			for(int k=0; k<cloud.size(); k+=2) {
				map[cloud.get(k)][cloud.get(k+1)]++;
			}

			//3. 구름이 모두 사라진다
			
			//4. 물복사버그 마법을 실행한다
			for(int k=0; k<cloud.size(); k+=2) {
				for(int p=1; p<8; p+=2) {
					int ddr = cloud.get(k)+r[p];		//r
					int ddc = cloud.get(k+1)+c[p];		//c
					
					if(!(0<ddr && ddr<=n && 0<ddc && ddc<=n)) continue;
					if(map[ddr][ddc]>0) map[cloud.get(k)][cloud.get(k+1)]++;
				}				
			}

			//현재 구름 좌표가 있는 리스트 비우기
			cloud.clear();

			//5. 물의 양이 2 이상이면 물이 2 감소한다 > 3번의 구름 제외
			for(int p=0; p<n+1; p++) {
				for(int k=0; k<n+1; k++) {
				
					if(isvisited[p][k]) continue;
					
					if(map[p][k]>=2) {
						map[p][k]-=2;
						cloud.add(p);
						cloud.add(k);
					}
				}
			}
		}
		
		
		//값 더하고 출력
		int result=0;
		for(int p=1; p<n+1; p++) {
			for(int k=1; k<n+1; k++) {
				result+=map[p][k];
			}
		}
        
		System.out.println(result);
		
	}
}

 

 

(❁´◡`❁)

끝!