[BOJ 19237] 어른 상어 (Java)

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

19237번: 어른 상어

import java.util.Scanner;

public class P19237 {
	static int N, M, k;
	static Info[][] board;
	static Shark[] sharks;
	static int[][][] priority;
	static Shark[] save;
	static int[] dr= {0,-1,1,0,0};
	static int[] dc= {0, 0, 0, -1,1};
	static int count;
	static int time=0;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int temp;
		int answer=-1;
		N=sc.nextInt(); 
		M=sc.nextInt();
		k=sc.nextInt();
		board=new Info[N][N];
		sharks=new Shark[M+1];
		priority=new int[M+1][5][4];
		save=new Shark[M+1];
		count=M;
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				temp=sc.nextInt();
				if (temp==0) {
					board[i][j]=new Info(0,0);
				}
				else {
					board[i][j]=new Info(temp,k);
					sharks[temp]=new Shark(i,j,0);
					save[temp]=new Shark(i,j,0);
				}
			}
		}
		for (int i=1; i<=M; i++) {
			sharks[i].dir=sc.nextInt();
		}
		for (int i=1; i<=M; i++) {
			for (int j=1; j<=4; j++) {
				for (int k=0; k<4; k++) {
					priority[i][j][k]=sc.nextInt();
				}
			}
		}
		while (time<=1000) {
			if (count==1) {
				answer=time;
				break;
			}
			for (int i=1; i<=M; i++) {
				if (sharks[i].dir==0) {
					continue;
				}
				if (!isNoSmell(i)) {
					isMySmell(i);
				}
			}
			move();
			time++;
		}
		System.out.println(answer);
	}
	
	
	static boolean isNoSmell(int num) {
		boolean flag=false;
		int now_dir=sharks[num].dir;
		int now_r=sharks[num].r;
		int now_c=sharks[num].c;
		int new_dir, new_r, new_c;
		for (int i=0; i<4; i++) {
			new_dir=priority[num][now_dir][i];
			new_r=now_r+dr[new_dir];
			new_c=now_c+dc[new_dir];
			if (new_r<0 || new_c<0 || new_r>=N || new_c>=N) {
				continue;
			}
			if (board[new_r][new_c].smell==0) { 
				flag=true;
				save[num].r=new_r;
				save[num].c=new_c;
				save[num].dir=new_dir;
				break;
			}
		}
		return flag;
	}
	
	static boolean isMySmell(int num) {
		boolean flag=false;
		int now_dir=sharks[num].dir;
		int now_r=sharks[num].r;
		int now_c=sharks[num].c;
		int new_dir, new_r, new_c;
		for (int i=0; i<4; i++) {
			new_dir=priority[num][now_dir][i];
			new_r=now_r+dr[new_dir];
			new_c=now_c+dc[new_dir];
			if (new_r<0 || new_c<0 || new_r>=N || new_c>=N) {
				continue;
			}
			if (board[new_r][new_c].shark_num==num && board[new_r][new_c].smell>0) {
				save[num].r=new_r;
				save[num].c=new_c;
				save[num].dir=new_dir;
				flag=true;
				break;
			}
		}
		return flag;
	}
	
	static void move() {
		int nr, nc, ndir;
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (board[i][j].smell>0) {
					board[i][j].smell-=1;
					if (board[i][j].smell==0) {
						board[i][j].shark_num=0;
					}
				}
			}
		}
		for (int i=1; i<=M; i++) {	//이동한 칸에 냄새 뿌리고 & 상어 이동해주기 
			if (sharks[i].dir==0) {
				continue;
			}
			nr=save[i].r;
			nc=save[i].c;
			ndir=save[i].dir;
			if (board[nr][nc].shark_num!=0 && board[nr][nc].shark_num!=i) { 
					count--;
					sharks[i].dir=0;		//쫓겨남 처리
					continue;
			}
			board[nr][nc].shark_num=i;
			board[nr][nc].smell=k;
			sharks[i].r=nr;
			sharks[i].c=nc;
			sharks[i].dir=ndir;
		}
	}
	
	static public class Shark{
		int r;
		int c;
		int dir;
		public Shark(int r, int c, int dir) {
			this.r = r;
			this.c = c;
			this.dir = dir;
		}
		
	}
	static public class Info{
		int shark_num;
		int smell;
		public Info(int shark_num, int smell) {
			this.shark_num = shark_num;
			this.smell = smell;
		}
	}

}

사소한 실수+범위 문제때문에 삽질을 했던 문제.

 

우선순위를 배열에 넣어놓고, 인접 빈칸 먼저 탐색하고->이동할 빈칸이 없으면 자기 냄새 있는 인접 공간을 탐색하는 식으로 진행한다.

죽은 shark는 direction을 0으로 설정해줘서 추후에 탐색되는 것을 막는다.

 

상어의 이동할 위치를 save배열에 저장한 후 나중에 한꺼번에 이동하는 방식을 취한다.

1번부터 옮겨줘서 이동할 위치에 만약 빈칸이 아니고 다른 상어가 있으면 그 상어를 죽은 상어 처리해준다.

 

구현 문제라 적절한 자료 구조 선정+사소한 실수를 하지 않는 것이 중요했다.