Life Engineering
[BOJ 19237] 어른 상어 (Java) 본문
https://www.acmicpc.net/problem/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 인 경우를 체크해주면 된다.
이러면 별도로 따로 감소해줄 필요도 없다..
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 카드 짝 맞추기 (Java) (0) | 2022.05.05 |
---|---|
[BOJ 13460] 구슬 탈출2 (Java) (0) | 2022.04.29 |
[BOJ 23289] 온풍기 안녕! (Java) (0) | 2022.04.26 |
[BOJ 15684] 사다리 조작 (Java) (0) | 2022.04.23 |
[프로그래머스] N으로 표현 (Java) (0) | 2022.04.23 |