[BOJ 19237] 어른 상어 (Java)

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

19237번: 어른 상어

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

public class Main_BOJ_19237 {
	static class Pos{
		int smell_time;	//smell 시간
		int shark_num;	//smell 뿌린 shark number
		public Pos(int smell_time, int shark_num){
			this.smell_time=smell_time;
			this.shark_num=shark_num;
		}
	}
	static class Shark{
		int r, c, d;
		boolean isDead;
		public Shark(int r, int c, int d) {
			this.r = r;
			this.c = c;
			this.d = d;
			this.isDead=false;
		}
	}
	static int N, M, k;
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int[][][] priorities;
	static Shark[] sharks;
	static Pos[][] map;
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		M=Integer.parseInt(st.nextToken());
		k=Integer.parseInt(st.nextToken());
		priorities=new int[M+1][4][4];		//상어 번호는 1번부터 시작
		map=new Pos[N][N];
		sharks=new Shark[M+1];
		for (int i=0; i<N; i++) {
			st=new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				int x=Integer.parseInt(st.nextToken());
				if (x==0) {
					map[i][j]=new Pos(0, 0);
				}
				else if (x!=0) {
					map[i][j]=new Pos(k, x);
					sharks[x]=new Shark(i, j, 0);
				}
			}
		}
		st=new StringTokenizer(br.readLine());
		for (int i=1; i<=M; i++) {
			sharks[i].d=Integer.parseInt(st.nextToken())-1;
		}
		for (int i=1; i<=M; i++) {
			for (int j=0; j<4; j++) {
				st=new StringTokenizer(br.readLine());
				for (int d=0; d<4; d++) {
					int p=Integer.parseInt(st.nextToken())-1;
					priorities[i][j][d]=p;	//i번 상어가 j 방향 향하고 있을 때 우선순위
				}
			}
		}
		int answer=0;
		while (true) {
			sharkMove();
			answer++;
			if (check()) break;
			if (answer>1000) break;
		}
		System.out.println(answer==1001?-1:answer);

	}
	
	private static boolean check() {
		for (int i=2; i<=M; i++) {
			if (!sharks[i].isDead) return false;
		}
		return true;
	}
	
	private static void sharkMove() {
		Pos[][] temp=new Pos[N][N];
		for (int i=0; i<N; i++) {
			for (int j=0; j<N; j++) {
				if (map[i][j].smell_time>0) {
					temp[i][j]=new Pos(map[i][j].smell_time-1, map[i][j].shark_num);
					if (temp[i][j].smell_time==0) temp[i][j].shark_num=0;
				}
				else {
					temp[i][j]=new Pos(0, 0);
				}
			}
		}
		int r, c, d, nd, nr, nc, blank, mysmell, new_dir;
		for (int i=1; i<=M; i++) {
			if (sharks[i].isDead) continue;
			new_dir=-1; blank=-1; mysmell=-1;		//빈칸, 자기냄새 칸 있는 방향
			r=sharks[i].r;
			c=sharks[i].c;
			d=sharks[i].d;
			for (int j=0; j<4; j++) {		//인접 방향을 보면서 이동할 공간 찾는다
				nd=priorities[i][d][j];
				nr=r+dr[nd];
				nc=c+dc[nd];
				if (nr<0 || nc<0 || nr>=N || nc>=N) continue;
				if (map[nr][nc].shark_num==0 && blank==-1) blank=nd;
				else if (map[nr][nc].shark_num==i && mysmell==-1) mysmell=nd;
			}
			if (blank!=-1) {	//빈칸 있으면 그곳으로
				new_dir=blank;
			}
			else if (mysmell!=-1){
				new_dir=mysmell;
			}
			if (new_dir!=-1) {		//이동이 가능한 경우
				nr=r+dr[new_dir];
				nc=c+dc[new_dir];
				if (temp[nr][nc].shark_num==0 || temp[nr][nc].shark_num==i) {	//새롭게 냄새 넣어줌
					temp[nr][nc].shark_num=i;
					temp[nr][nc].smell_time=k;
					sharks[i].r=nr; sharks[i].c=nc;
					sharks[i].d=new_dir;
				}
				else {		//있을 경우
					sharks[i].isDead=true;
				}
			}
		}
		map=temp;
		
	}

}

 

 

구현, 시뮬레이션 문제..

 

자료구조는 다음과 같다:

class Shark: 상어의 위치, 방향, 죽음 여부를 나타내는 클래스

class Pos: 각 map의 한 칸에 위치한 smell 시간, smell 뿌린 상어의 번호를 저장

int[][][] priorities: 각 우선순위를 저장하는 배열, priorities[i][a][b]: i번 상어가 a 방향을 바라보고 있을 때 b번째 우선순위를 갖는 방향

Shark[] sharks: 상어들의 목록 sharks[i]: i번 상어의 정보를 담고 있음

Pos[][] map: 각 칸의 정보를 담음

 

sharkMove() 함수: temp 배열을 선언 후, 원래 map 배열의 내용을 복사한다 => 단, smell은 -1 해주고 만약 이 smell이 0이라면 냄새가 사라진 것이므로 shark_num=0 으로 초기화해준다.

sharks 배열을 순회하면서 저장한 우선순위대로 탐색하면서, 이동할 공간 있는지 찾는다

=>빈칸이 존재할 경우 첫번째 빈칸 나온 방향을 blank에 저장한다

=>자기 냄새가 있는 경우도 mysmell에 저장하여 마찬가지로 해준다

blank가 갱신되었을 경우 그쪽 방향으로 움직이고, blank 갱신이 안되고 mysmell 만 되었을 경우 그쪽 방향으로 움직인다. 

temp배열의 새로운 위치에 그 상어의 번호를 써주고, 냄새도 k로 써준다. 상어의 정보를 갖는 sharks[i] 위치정보, 방향정보도 갱신한다. 이때, 만약 temp 배열에 다른 상어의 번호가 쓰여 있을경우, 번호가 작은 상어가 먼저 그곳을 차지한 경우이므로 이때는 해당 상어를 isDead=true 해주어서 죽음 처리 해준다.

temp배열을 map 배열에 대입한다. 

 

다른 분의 코드를 보니, 

(https://yabmoons.tistory.com/496)

별도의 temp 배열을 만들어 줄 필요 없이 smell_time의 값을 갱신해주는 방식으로 진행했다. 상어가 있는 곳에서, 현재 타임+k 해서 업데이트해주고, 빈칸인지 체크는 현재 시간>=smell_time 인 경우를 체크해주면 된다.  

이러면 별도로 따로 감소해줄 필요도 없다..