[백준 19237번] 어른 상어 (java)

 

19237번: 어른 상어

 

int[][] resttime = new int[N+1][N+1] : 각 칸마다 냄새가 없어지기까지 남은 시간

 

int[][] smell = new int[N+1][N+1] : 각 칸에의 냄새를 뿌린 상어의 번호(냄새가 없으면 0)

 

int[][][] priority = new int[M+1][5][4] : 상어마다 현재 방향에서의 우선순위 

ex) priority[m][1][0] : m번 상어의 현재 방향이 위쪽방향(1)일 때, 0번째 우선순위에 해당하는 방향

 

Shark[] shark = new Shark[M+1] : 1번부터 M번까지 각 상어의 위치(r,c)와 방향(d) 정보

static class Shark {

	int r, c, d;

	Shark(int r, int c, int d) {
		this.r = r;
		this.c = c;
		this.d = d;
	}
}

 

 

1. 상하좌우 중에서 상어의 새로운 이동 위치(nr, nc)를 찾는다. 

 

   1-1. 상어의 현재 방향을 기준으로 가장 우선순위가 높은 방향부터 탐색한다.

         탐색 도중, 냄새가 없고 인접한 위치를 찾으면 탐색을 종료한다.

 

   2-1. 만약 모두 탐색했는데 냄새가 없는 곳이 없다면, 자기 자신의 냄새가 있는 인접한 곳을 찾는다.

         마찬가지로 현재 방향을 기준으로 가장 우선순위가 높은 방향부터 탐색한다.

		boolean flag = false;

		// 1-1. 높은 우선순위부터 차례대로 탐색
		for (int i = 0; i < 4; i++) {

			d = priority[m][shark[m].d][i];
			nr = shark[m].r + dr[d];
			nc = shark[m].c + dc[d];

			// 경계를 벗어나지 않으면서, 냄새가 없는 곳을 찾으면 break로 빠져나옴
			if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && smell[nr][nc] == 0) {
				flag = true;
				break;
			}
		}

		// 1-2. 냄새가 없는 곳이 없는 경우
		if (!flag) {
			for (int i = 0; i < 4; i++) {

				d = priority[m][shark[m].d][i];
				nr = shark[m].r + dr[d];
				nc = shark[m].c + dc[d];

				if ((1 <= nr && nr <= N) && (1 <= nc && nc <= N) && smell[nr][nc] == m)
					break;
			}
		}

 

2. 새로 이동하게 될 위치에 이미 다른 상어가 있는지 확인해야 한다. 

 

   tmp라는 임시 2차원 배열에는 현재 상어보다 이전에 움직인 상어가 이동한 결과가 들어있다.

   만약 현재 상어가 4번이고, 이 직전에 3번 상어가 (2, 4)로 이동을 한 상태라면 tmp[2][4]에는 3번 상어의

   번호인 3이 들어있다. -> tmp[2][4] = 3

  

   만약, 4번 상어도 이동 후 위치가 (2, 4)라면 한 곳에 두 마리 이상의 상어가 존재하게 된다.

   이런 경우를 대비에 각 케이스별로 별도의 처리를 해주었다.

 

   tmp[nr][nc] = 0 :

   이전에 (nr, nc)로 이동한 상어가 없다는 뜻이므로 tmp[nr][nc]에 현재 상어의 번호를 넣어준다.

   그리고 상어가 이동했으므로 현재 상어의 위치 정보와 방향 정보를 변경해준다.

   shark[m].r = nr;

   shark[m].c = nc;

   shark[m].d = d;

 

   tmp[nr][nc] != 0 : 

   이전에 (nr, nc)로 이동한 상어가 존재한다. 이전 상어의 번호는 현재 상어보다 작다. 즉, 현재 

   상어가 힘이 더 약하기 때문에 현재 상어는 문제 조건에 따라 경계 밖으로 쫓겨나게 된다.

   여기서 경계 밖으로 쫓겨나나 상어는 상어 번호(n)에 대하여 shark[n] = null로 나타내었다.

   따라서, 이 경우 shark[현재 상어 번호] = null로 설정한다.

		if (tmp[nr][nc] == 0) {

			tmp[nr][nc] = m;
			shark[m].r = nr;
			shark[m].c = nc;
			shark[m].d = d;
		}

		else {
			shark[m] = null;
		}

 

 

3. M마리의 상어 모두 이동을 완료하고 나면, 각 칸마다 냄새 정보를 업데이트 해야 한다.

 

   시간이 하나 지났으므로 냄새의 유효시간(resttime)을 하나씩 빼줘야 한다.

   만약, 어떤 칸의 resttime[i][j] = 0 이라면 유효시간이 끝난 것이므로 해당 위치의 냄새를 0으로 바꿔준다.

		// 냄새 유효기간 하나씩 줄이기
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (resttime[i][j] > 0)
					resttime[i][j]--;

				if (resttime[i][j] == 0)
					smell[i][j] = 0;
			}
		}

 

4. 상어가 모두 이동하고 난 후, 상어의 새로운 위치의 냄새 정보와 유효기간을 설정해준다.

 

   아까 상어가 이동하면서 이동한 결과를 tmp 2차원 배열에 저장했었다.

   tmp 2차원 배열을 하나씩 탐색하면서, (i, j)위치에 있는 상어 번호를 확인한 후,

   해당 위치의 냄새 유효기간(resttime[i][j])을 k로 설정하고, 냄새(smell[i][j])도 상어 번호를 넣어준다.

		// 이동후의 상어 위치의 냄새 정보와 유효기간 초기화하기
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (tmp[i][j] > 0) { // 0보다 크다는 것은 상어가 (i,j)에 새롭게 이동했음을 의미
					resttime[i][j] = k;
					smell[i][j] = tmp[i][j];
				}
			}
		}

 

 

1, 2, 3, 4번 과정을 time이 1000이 되거나 혹은 1번 상어가 남을 때까지 반복한다.

 

 

전체 코드 :