어른 상어

상어가 이동할 때마다 (상어 번호, 냄새지속k)를 저장해야한다고 생각했다.

Solution

(x,y) 위치에서 상어의 번호 뿐만 아니라, 현재 상어의 위치도 저장해야한다. 즉, 저장해야하는 것을 나열해보면 (x,y) 위치에서 ① 몇 번 상어가 존재하는지 ② 몇 번 상어의 냄새가 존재하는지 ③ 냄새의 강도

=>3차원 배열을 생성하여 1,2,차원은 x,y좌표를 의미하고, 3차원은 각각 ①, ②, ③을 저장한다! ex) Board[N][N][3] Board[x][y][0] : (x,y)에 있는 상어의 번호 Board[x][y][1] : (x,y)에 있는 냄새의 상어 번호 Board[x][y][2] : (x,y)에 있는 냄새의 강도 // 이동할 때마다 1씩 감소.

상어 클래스 정의 (x,y) 좌표, 방향, 방향 우선순위 배열 4x4

시간 복잡도

움직이는 최대 횟수는 1000이다.(문제에서 1000초가 지나면 -1을 리턴하도록 되어있기 때문.) 상어는 최대 400마리 존재, 이동가능한 방향은 4방향. 움직임에 대한 규칙은 2가지. (①빈칸으로 이동, ②빈칸이 없다면 본인의 냄새 쪽으로 이동) =>1000 * 400 * 4 * 2 = 3,200,000(320만 정도) << 1억. 그리고 이동하면서 상어 갯수 줄어든다.

입력받을 것이 많기 때문에 데이터를 어떻게 저장할지도 고려할 요소인 것 같다.

1. 자료구조 선언 : 상어 클래스에 4가지 방향일 때 우선순위 방향을 저장하는 4x4크기 배열도 함께 속성으로 만들어준다!

2. 알고리즘 전체 구조 1. 입력받을 때, 1부터 시작하는 걸로 되어있는데 0-based index를 사용할 것이기 때문에 1씩 감산 처리해준다! 입력으로 주어지는 Map을 입력받을 때, 값이 0이 아니면 상어의 번호를 의미하기 때문에 그 때의 (i,j) 상어의 현재 위치를 3차원의 0번째 열에 저장한다! 상어들의 정보를 저장하는 배열에 각 상어 저장. 3차원 1번째 열, 3차원 2번째열에도 각각 해당하는 값을 넣어준다! (초기에는 [1] = [0], [2] = k) 2. 각 상어의 현재의 방향 정보 저장 : i번째 상어 클래스 생성했으므로 방향 속성값으로 저장해주면 됨. 3. 방향 우선순위 저장 : Mx4 번 반복해야한다. 이에 따른 반복문 구성, 입력받아서 i번 상어 속성값(배열)에 저장해주면 된다.

3. 반복을 종료하는 조건 : 한번 이동할 때 time이 걸린다고 하면, time이 1000을 넘거나, 상어가 1마리만 남으면 종료=>죽는 상어의 갯수를 카운팅.

자료 구조 선언

소스 코드 전체 구조

시뮬레이션 solve 함수 반복 조건

이번 문제는 입력받는 부분이 많기 때문에, 이 부분을 잘 처리하는 것이 관건이다...!

문제에서 주어지는 조건들을 잘 활용해서 어떤 부분을 처리해야하고 어떤 부분은 적절히 넘어가도 되는지 판단하는 것도 중요하다. 한 칸에 2마리 이상의 상어가 존재한다면, 상어 번호가 작은 상어가 살아남는다. 이동을 반복하고 나서 최후에 남는 상어는 제일 최솟값 번호인 1번 상어가 된다.

각 상어의 이동을 반복하는 반복문을 증가하는 반복문으로 구성한다면 한 칸에 상어가 여러마리 존재하더라도 가장 최우선 순위의 상어를 먼저 이동하게 되는 것이기 때문에, 반복문을 거듭하면서 i번째 상어를 이동시킬 때, 인접 칸에 이미 다른 "상어가 존재"하거나, "상어의 냄새가 존재"한다면, 이전의 번호가 작은 상어가 우선적으로 존재하기 때문에 현재의 상어는 삭제 대상이 된다!

M개 상어의 방항 우선순위 정보 입력받는데에서 헤맨 부

//M개 상어 방향 우선순위 입력 받는다:M=4라면 16줄 입력받는다.
		for(int i=0;i<M*4;i++) {
			input = br.readLine().split(" ");
			int[][] tmp = new int[16][4];
			for(int j=0;j<4;j++) {
				tmp[i][j] = Integer.parseInt(input[j])-1;
				System.out.print(tmp[i][j]+" ");
			}
			System.out.println();
		}

헤매다가 가까스로(?) 구현 성공한 부분!

for(int m = 0;m<M;m++) {//M번 반복.
			Shark cur = sharkArr[m];
			int[][] tmp = new int[4][4];
			for(int i=0;i<4;i++) {
				input = br.readLine().split(" ");
				for(int j=0;j<4;j++) {
					tmp[i][j] = Integer.parseInt(input[j])-1;
					//System.out.print(tmp[i][j]+" ");
				}
				//System.out.println();
			}
			cur.Dir = tmp;
		}

리팩토링 :

for(int m = 0;m<M;m++) {//M번 반복.
			Shark cur = sharkArr[m];
			for(int i=0;i<4;i++) {
				input = br.readLine().split(" ");
				for(int j=0;j<4;j++) {
					cur.Dir[i][j] = Integer.parseInt(input[j])-1;
				}
			}
		}

구현해야하는 것을 명확하게 하기.

1. 남은 상어 갯수가 1개(삭제한 상어 갯수 M-1개)이면 종료

2. time이 1000 초과하면 종료

3. 이동할 때마다 time이 +1씩 증가

4. 경우에 따라 상어 삭제 - 삭제하는 상어 갯수 카운팅